CODEWITHSUNDEEP
c
user950356
user950356

Reputation:

Matrix-Matrix Multiplication

I'm writing a C code including matrix multiplication and I'm using 3 nested loops for that operation. So, does anyone know how we can improve that code by removing one of the nested loops?

for (i = 0; i < SIZE; ++i)
    for (j = 0; j < SIZE; ++j)
        for (k = 0; k < SIZE; ++k)
            c[i][j] += a[i][k] * b[k][j];

Upvotes: 1

Views: 3021

Answers (2)

hwasungmars
hwasungmars

Reputation: 11

Strassen algorithm is a classic one to try.

http://en.wikipedia.org/wiki/Strassen_algorithm

It is more complicated than writing three loops and the overall speed gain might not show through if the matrix size is small.

As far as I know, Mathematica and Matlab use the three nested loop multiplication for small matrices and switch to Strassen for larger ones.

There are other algorithms that theoretically perform better asymptotically, but unless you are doing very very large matrix multiplication, I don't think it will help that much.

Upvotes: 1

Zeta
Zeta

Reputation: 105886

Matrix multiplication for dense matrices has O(n^3). This can be accelerated by using Strassen's algorithm to O(n^(2.8)) or Coppersmith-Winogar to O(n^(2.37)).

Upvotes: 3

Related Questions