Strassen's matrix multiplication program in c







C code of two 2 by 2 matrix multiplication using Strassen algorithm:


#include<stdio.h>
int main(){
  int a[2][2],b[2][2],c[2][2],i,j;
  int m1,m2,m3,m4,m5,m6,m7;

  printf("Enter the 4 elements of first matrix: ");
  for(i=0;i<2;i++)
      for(j=0;j<2;j++)
           scanf("%d",&a[i][j]);

  printf("Enter the 4 elements of second matrix: ");
  for(i=0;i<2;i++)
      for(j=0;j<2;j++)
           scanf("%d",&b[i][j]);

  printf("\nThe first matrix is\n");
  for(i=0;i<2;i++){
      printf("\n");
      for(j=0;j<2;j++)
           printf("%d\t",a[i][j]);
  }

  printf("\nThe second matrix is\n");
  for(i=0;i<2;i++){
      printf("\n");
      for(j=0;j<2;j++)
           printf("%d\t",b[i][j]);
  }

  m1= (a[0][0] + a[1][1])*(b[0][0]+b[1][1]);
  m2= (a[1][0]+a[1][1])*b[0][0];
  m3= a[0][0]*(b[0][1]-b[1][1]);
  m4= a[1][1]*(b[1][0]-b[0][0]);
  m5= (a[0][0]+a[0][1])*b[1][1];
  m6= (a[1][0]-a[0][0])*(b[0][0]+b[0][1]);
  m7= (a[0][1]-a[1][1])*(b[1][0]+b[1][1]);

  c[0][0]=m1+m4-m5+m7;
  c[0][1]=m3+m5;
  c[1][0]=m2+m4;
  c[1][1]=m1-m2+m3+m6;

   printf("\nAfter multiplication using \n");
   for(i=0;i<2;i++){
      printf("\n");
      for(j=0;j<2;j++)
           printf("%d\t",c[i][j]);
   }

   return 0;
}

Sample output:
Enter the 4 elements of first matrix: 1
2
3
4
Enter the 4 elements of second matrix: 5
6
7
8

The first matrix is

1       2
3       4
The second matrix is

5       6
7       8
After multiplication using

19      22
43      50








Alogrithm:
**







5 comments:

  1. actually what's the rule of strassen matrix?
    I don't understand it's mathmatic prograssion.

    ReplyDelete
  2. this program is implemented with 2x2 matrices. but how to implement mxn & pxq matrix multiplication???? please elp.

    ReplyDelete
  3. write the c code for n x n matrix

    ReplyDelete
  4. When Strassen suggested this algorithm, he never really gave a formal proof as to how he came up with it. All that is known is that the algorithm works and only for nxn matrices where n should be a power of 2.

    ReplyDelete