# Fast algorithm for computing matrix multiplication!!!!

Discussion in 'C' started by asadullah.ansari, Jan 16, 2008.

Joined:
Jan 9, 2008
Messages:
356
14
Trophy Points:
0
Occupation:
Developer
Location:
NOIDA
Mostly people are using this algorithm to compute matrix multiplication:

Code:
```#define n 1000
int main()
{
int a[n][n],b[n][n],c[n][n];
c=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:
```#define n 1000
#define BlockSize  100
int main()
{
int a[n][n],b[n][n],c[n][n];
c=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;
}
```

Last edited: Jan 16, 2008
2. ### debleena_doll2002New Member

Joined:
Feb 5, 2008
Messages:
119
0
Trophy Points:
0
Yes!!! But can you tell me how's senario of Catche memory here?

Joined:
Jul 12, 2004
Messages:
15,374
388
Trophy Points:
83
You can create a thread in the right category and it does not seem the right place.

4. ### crazytolearn57New Member

Joined:
Feb 14, 2008
Messages:
48
0
Trophy Points:
0
i didnt understand

5. ### parvez.yuNew Member

Joined:
Feb 14, 2008
Messages:
100
0
Trophy Points:
0
nice

6. ### aisha.ansari84New Member

Joined:
Feb 13, 2008
Messages:
82
1
Trophy Points:
0
i feel its a reall nice way,good one

7. ### alrameshNew Member

Joined:
Feb 5, 2008
Messages:
22
0
Trophy Points:
0
i m not getting at all.

8. ### alrameshNew Member

Joined:
Feb 5, 2008
Messages:
22
0
Trophy Points:
0
Can you explain more about Block Algorithm?

Joined:
Feb 13, 2008
Messages:
103