Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to optimize matrix multiplication operation [duplicate]

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.

like image 390
george Avatar asked May 19 '11 16:05

george


People also ask

How is matrix multiplication optimized?

Once a block version of the matrix-matrix multiplication is implemented, one typically further optimize the algorithm by unrolling the innermost loop (i.e., instead of using a for loop to do 8 updates, one write the 8 updates directly in the program) to help the compiler to pipeline the instructions to the CPU.

What is the best algorithm for matrix multiplication?

In linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm for matrix multiplication. It is faster than the standard matrix multiplication algorithm for large matrices, with a better asymptotic complexity, although the naive algorithm is often better for smaller matrices.

What is the best time complexity for matrix multiplication?

This is a major open question in theoretical computer science. As of December 2020, the matrix multiplication algorithm with best asymptotic complexity runs in O(n2.3728596) time, given by Josh Alman and Virginia Vassilevska Williams.


2 Answers

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;
}
like image 119
Arlen Avatar answered Oct 26 '22 23:10

Arlen


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.

like image 35
jedwards Avatar answered Oct 26 '22 22:10

jedwards