Strassen’s Algorithm in C

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.

```
/*
```

C code of two 2 by 2 matrix multiplication using Strassen's 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 Strassen's algorithm \n");

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

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

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

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Gauss Seidel Method

» Next - C Program to Perform Complex Number Multiplication

Related Posts:

Check Computer Science Books
Practice BCA MCQs
Check C Books
Practice Computer Science MCQs
Apply for C Internship

Recommended Articles: