# 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. }

\$ 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.