Sunday, February 14, 2010

Fast Algorithm for Computing Matrix Multiplication!!!!

Mostly people are using this algorithm to compute matrix multiplication:


Code: C

#define n 1000 int main() { int a[n][n],b[n][n],c[n][n]; c[0][0]=0; for( i=0;i) { for(j=0;j) { for(k=0;k) { c[i][j] = c[i][j] + a[i][k] * b[k][j] } } } return 0; }

In this program( a short algo) , every time we are taking one element of an array to catche and processing for it. Means At one time cpu reading one element value of a array and b Array and compute and store to c Array.


To reading every time elements from array , why we are taking some group of element i.e. Block size, then no need to read every element. A groups of element will be on catche and we can do fast as given above algo. This algorithm called " Block Algorithm". This Block algorithm can be applied many place where this type of situation will come.


Block Algorithm for Matrix Multiplication:

Code: C

#define n 1000 #define BlockSize 100 int main() { int a[n][n],b[n][n],c[n][n]; c[0][0]=0; for( i1=0;i1<(n/BlockSize);++i1) { for(j1=0;j1<(n/BlockSize);++j1) { for(k1=0;k1<(n/BlockSize);++k1) { for(i=i1=0;i(i1+BlockSize-1);++i) { for(j=j1=0;j(j1+BlockSize-1);++j) { for(k=k1;k(k1+BlockSize-1);++k) { c[i][j] = c[i][j] + a[i][k] * b[k][j] } } } } } } return 0; }

No comments: