Go4Expert - Fast algorithm for computing matrix multiplication!!!!

Go4Expert (http://www.go4expert.com/)

- C (http://www.go4expert.com/forumdisplay.php?f=60)

- - Fast algorithm for computing matrix multiplication!!!! (http://www.go4expert.com/showthread.php?t=8284)

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<n;++i)
    {
        for(j=0;j<n;++j)
        {
            for(k=0;k<n;++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<min(i1+BlockSize-1);++i)
                {
                    for(j=j1=0;j<min(j1+BlockSize-1);++j)
                    {
                        for(k=k1;k<min(k1+BlockSize-1);++k)
                        {               
                            c[i][j] = c[i][j] + a[i][k] * b[k][j]
                        }
                    }
                }
            }
        }
           }
 return 0;
}