Algorithm and Program for Strassen's matrix multiplication

Algorithm

If the sizes of A and B are less than the threshold

Compute C = AB using the traditional matrix multiplication algorithm.
Else use Strassen's algorithm
Split matrices A and B
For each of

Mi i = 1 to 7

Create a new thread to compute

Mi = A'i B'i

If the sizes of the matrices are less than the threshold
Compute C using the traditional matrix multiplication algorithm.
Else use Strassen's algorithm
Split matrices A'

i and B'i

For each of M

ij j = 1 to 7

If i=7 and j=7 go to step 1 with A = A'77

and

B = B'77

Get a thread from the thread pool to compute

M= A'ij B'ij

Execute the recursive version of Strassen's algorithm in this thread
Wait for the Mij

threads to complete execution

Compute MiWait for the Mi

threads to complete execution

Compute C

Program

#include<iostream.h>

#include<conio.h>

void main()

{

int a[2][2],b[2][2],c[2][2],i,j;

int p1,p2,p3,p4,p5,p6,p7;

clrscr();

cout<<"enter the first matrix";

for(i=1;i<=2;i++)

for(j=1;j<=2;j++)

cin>>a[i][j];

cout<<"enter the second matrix";

for(i=1;i<=2;i++)

for(j=1;j<=2;j++)

cin>>b[i][j];

p1=a[1][1]*(b[1][2]-b[2][2]);

p2=(a[1][1]+a[1][2])*b[2][2];

p3=(a[2][1]+a[2][2])*b[1][1];

p4=a[2][2]*(b[2][1]-b[1][1]);

p5=(a[1][1]+a[2][2])*(b[1][1]+b[2][2]) ;

p6=(a[1][2]-a[2][2])*(b[2][1]+b[2][2]) ;

p7=(a[1][1]-a[2][1])*(b[1][1]+b[1][2]) ;

c[1][1]=p5+p4-p2+p6;

c[1][2]=p1+p2;

c[2][1]=p3+p4;

c[2][2]=p5+p1-p3-p7;

for(i=1;i<=2;i++)

{

for(j=1;j<=2;j++)

{

cout<<c[i][j]<<" ";

}

cout<<"\n" ;

}

getch();

}