How to optimize matrix multiplication operation

Question

I need to perform a lot of matrix operations in my application. The most time consuming is matrix multiplication. I implemented it this way

template<typename T>
Matrix<T> Matrix<T>::operator * (Matrix& matrix)
{


    Matrix<T> multipliedMatrix = Matrix<T>(this->rows,matrix.GetColumns(),0);

    for (int i=0;i<this->rows;i++)
    {
        for (int j=0;j<matrix.GetColumns();j++)
        {
            multipliedMatrix.datavector.at(i).at(j) = 0;
            for (int k=0;k<this->columns ;k++)
            {
                multipliedMatrix.datavector.at(i).at(j) +=  datavector.at(i).at(k) * matrix.datavector.at(k).at(j);
            }
            //cout<<(*multipliedMatrix)[i][j]<<endl;
        }
    }
    return multipliedMatrix;
}

Is there any way to write it in a better way?? So far matrix multiplication operations take most of time in my application. Maybe is there good/fast library for doing this kind of stuff ?? However I rather can't use libraries which uses graphic card for mathematical operations, because of the fact that I work on laptop with integrated graphic card.

In general, if you need a fairly standard thing done efficiently, you should look for a well-done library. They're written by people who typically know more than you do about the operation, and who can put in more time than you can making it efficient. — David Thornley, May 19 '11 at 16:56
Are these dense matrices? If not (in quite a lot of applications you have sparse matrices), this simple algorithm will waste a lot of time multiplying zeroes. Of course, in order to handle sparse matrices efficiently, you would need to completely change the way the data is stored. — leftaroundabout, May 19 '11 at 20:23
Check out the [Blaze library](https://bitbucket.org/blaze-lib/blaze/wiki/Benchmarks#!row-major-dense-matrixdense-matrix-multiplication), which handles matrix-matrix multiplication very well and provides an easy-to-use syntax. — Engineero, Aug 13 '18 at 13:30

Arlen · Answer 1 · 2011-05-19T16:57:20.070

Eigen is by far one of the fastest, if not the fastest, linear algebra libraries out there. It is well written and it is of high quality. Also, it uses expression template which makes writing code that is more readable. Version 3 just released uses OpenMP for data parallelism.

#include <iostream>
#include <Eigen/Dense>

using Eigen::MatrixXd;

int main()
{
  MatrixXd m(2,2);
  m(0,0) = 3;
  m(1,0) = 2.5;
  m(0,1) = -1;
  m(1,1) = m(1,0) + m(0,1);
  std::cout << m << std::endl;
}

score 4 · Answer 2 · answered May 19 '11 at 16:42

4

Boost uBLAS I think is definitely the way to go with this sort of thing. Boost is well designed, well tested and used in a lot of applications.

answered May 19 '11 at 16:42

Clinton

22,361
15
67
163

3

When compared to the other options that are available (Eigen, CUBLAS, MKL), Boost uBLAS has pretty terrible performance. Eigen in particular integrates many of the concepts used by Boost uBLAS, and can emit SIMD instructions for various CPU architectures. – void-pointer May 05 '12 at 22:57

jedwards · Answer 3 · 2011-05-19T16:53:36.903

Consider GNU Scientific Library, or MV++

If you're okay with C, BLAS is a low-level library that incorporates both C and C-wrapped FORTRAN instructions and is used a huge number of higher-level math libraries.

I don't know anything about this, but another option might be Meschach which seems to have decent performance.

Edit: With respect to your comment about not wanting to use libraries that use your graphics card, I'll point out that in many cases, the libraries that use your graphics card are specialized implementations of standard (non-GPU) libraries. For example, various implementations of BLAS are listed on it's Wikipedia page, only some are designed to leverage your GPU.

score 1 · Answer 4 · answered May 19 '11 at 16:46

There is a book called Introduction to Algorithms. You may like to check the chapter of Dynamic Programming. It has an excellent matrix multiplication algo using dynamic programming. Its worth a read. Well, this info was in case you want to write your own logic instead of using a library.

score 0 · Answer 5 · answered May 19 '11 at 16:47

0

There are plenty of algorithms for efficient matrix multiplication.

Algorithms for efficient matrix multiplication

Look at the algorithms, find an implementations.

You can also make a multi-threaded implementation for it.

answered May 19 '11 at 16:47

Yochai Timmer

48,127
24
147
185

How to optimize matrix multiplication operation

5 Answers5

Linked