   # Which order of loops is fastest in matrix multiplication and why ?

62 views
``````for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
C[i][j]+=A[i][k]*B[k][j];
``````

In this algorithm, there are 6 combinations of loops : the one given above is ijk. The others are ikj,jki,jik,kij and kji. Which one executes the fastest and why? posted Jun 29, 2016
Looking for an answer?  Promote on:
Similar Questions

suppose

``````A(n,m) =
1 2 3
4 5 6
7 8 9

and

B(p, q) =
1 1
1 1
``````

What is best method to find min of square of difference of sub-matrices of A and B e.g.

sub-matrices of A =

``````1 2    |     2 3   |    4 5    |   5 6
3 4    |     5 6   |    7 8    |   8 9
``````

Difference of first sub-matrix of A with B =

``````(1-1)  (2-1)    = |     0 1
(3-1)  (4-1)      |     2 3
``````

sum of square of elements = `0*0 + 1*1 + 2*2 + 3*3 = 14`

similar steps for other sub-matrices of A

Please suggest looking for an alternate method or algorithm which has time complexity less than `O(n*m*p*q)`