Question Name:Matrix Multiplication-Strassen

``````#include <iostream>
using namespace std;
int main()
{
int avi[50][50],b[50][50],c,d,i,size,k,p[50][50],sum=0;

cin>>size;

for(c=0;c<size;c++ )
{
for(d=0;d<size;d++)
{
cin>>avi[c][d];
}
}
for(c=0;c<size;c++ )
{
for(d=0;d<size;d++)
{
cin>>b[c][d];
}
}
for(c=0;c<size;c++ )
{
for(d=0;d<size;d++) //00*00+ 01*10 , 00*01 + 01*11
{
for(k=0;k<size;k++)
{
sum=sum+avi[c][k]*b[k][d];
}
p[c][d]=sum;
sum=0;
}
}
for(c=0;c<size;c++ )
{
for(d=0;d<size;d++)
{
cout<<p[c][d]<<" ";
} cout<<endl;
}
return 0;
}``````
• Problem Description
Write a program to compute product of two matrices using Strassen Multiplication algorithm. Here the dimensions of matrices must be a power of 2.

1) Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below diagram.
2) Calculate following values recursively. ae + bg, af + bh, ce + dg and cf + dh.

Input Format:
Order of the matrix
Enter the elements of matrix 1
Enter the elements of matrix 2
• Test Case 1
Input (stdin)2
1 2
3 4
5 6
7 8
Expected Output19 22
43 50
• Test Case 2
Input (stdin)2
4 2
1 4
2 6
1 4
Expected Output10 32
6 22