Fast algorithm for computing matrix multiplication!!!!

asadullah.ansari's Avatar author of Fast algorithm for computing matrix multiplication!!!!
This is an article on Fast algorithm for computing matrix multiplication!!!! in C.
Rated 5.00 By 3 users
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;
}
debleena_doll2002's Avatar
Ambitious contributor
Yes!!! But can you tell me how's senario of Catche memory here?
shabbir's Avatar, Join Date: Jul 2004
Go4Expert Founder
Quote:
Originally Posted by debleena_doll2002
Yes!!! But can you tell me how's senario of Catche memory here?
You can create a thread in the right category and it does not seem the right place.
crazytolearn57's Avatar, Join Date: Feb 2008
Go4Expert Member
i didnt understand
parvez.yu's Avatar, Join Date: Feb 2008
Ambitious contributor
nice
aisha.ansari84's Avatar, Join Date: Feb 2008
Contributor
i feel its a reall nice way,good one
alramesh's Avatar
Go4Expert Member
i m not getting at all.
alramesh's Avatar
Go4Expert Member
Can you explain more about Block Algorithm?
rahul.mca2001's Avatar, Join Date: Feb 2008
Ambitious contributor
Quote:
Originally Posted by alramesh
Can you explain more about Block Algorithm?
what is Block Algorithm