C Program to Implement Strassen’s Algorithm

«
»
This C program implements Strassen’s algorithm to multiply two matrices. This is a program to compute product of two matrices using Strassen Multiplication algorithm. Here the dimensions of matrices must be a power of 2.

Here is the source code of the C program to multiply 2*2 matrices using Strassen’s algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2. C code of two 2 by 2 matrix multiplication using Strassen's algorithm
  3. */
  4. #include<stdio.h>
  5. int main(){
  6.   int a[2][2], b[2][2], c[2][2], i, j;
  7.   int m1, m2, m3, m4 , m5, m6, m7;
  8.  
  9.   printf("Enter the 4 elements of first matrix: ");
  10.   for(i = 0;i < 2; i++)
  11.       for(j = 0;j < 2; j++)
  12.            scanf("%d", &a[i][j]);
  13.  
  14.   printf("Enter the 4 elements of second matrix: ");
  15.   for(i = 0; i < 2; i++)
  16.       for(j = 0;j < 2; j++)
  17.            scanf("%d", &b[i][j]);
  18.  
  19.   printf("\nThe first matrix is\n");
  20.   for(i = 0; i < 2; i++){
  21.       printf("\n");
  22.       for(j = 0; j < 2; j++)
  23.            printf("%d\t", a[i][j]);
  24.   }
  25.  
  26.   printf("\nThe second matrix is\n");
  27.   for(i = 0;i < 2; i++){
  28.       printf("\n");
  29.       for(j = 0;j < 2; j++)
  30.            printf("%d\t", b[i][j]);
  31.   }
  32.  
  33.   m1= (a[0][0] + a[1][1]) * (b[0][0] + b[1][1]);
  34.   m2= (a[1][0] + a[1][1]) * b[0][0];
  35.   m3= a[0][0] * (b[0][1] - b[1][1]);
  36.   m4= a[1][1] * (b[1][0] - b[0][0]);
  37.   m5= (a[0][0] + a[0][1]) * b[1][1];
  38.   m6= (a[1][0] - a[0][0]) * (b[0][0]+b[0][1]);
  39.   m7= (a[0][1] - a[1][1]) * (b[1][0]+b[1][1]);
  40.  
  41.   c[0][0] = m1 + m4- m5 + m7;
  42.   c[0][1] = m3 + m5;
  43.   c[1][0] = m2 + m4;
  44.   c[1][1] = m1 - m2 + m3 + m6;
  45.  
  46.    printf("\nAfter multiplication using Strassen's algorithm \n");
  47.    for(i = 0; i < 2 ; i++){
  48.       printf("\n");
  49.       for(j = 0;j < 2; j++)
  50.            printf("%d\t", c[i][j]);
  51.    }
  52.  
  53.    return 0;
  54. }

advertisement
$ gcc strassen.c -o strassen
$ ./strassen
 
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 Strassen's algorithm
 
19	22	
43	50

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Reference Books in C Programming, Data Structures and Algorithms.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter