DAA Strassen’s Matrix Multiplication

Home / Design and Analysis of Algorithms(DAA)-Tutorial / DAA Strassen’s Matrix Multiplication

Strassen’s Matrix Multiplication

Strassen in 1969 gave an overview on how we can find the multiplication of two 2*2 dimension matrices by the brute-force algorithm. But by using the divide and conquer technique the overall complexity for the multiplication of two matrices has been reduced. This happens by decreasing the total number of multiplications performed at the expense of a slight increase in the number of additions.

Strassen has used some formulas for multiplying the two 2*2 dimension matrices where the number of multiplications is seven, additions and subtractions are is eighteen, and in brute force algorithm, there is eight number of multiplications and four addition.

When the order n of matrix reaches infinity, the utility of Strassen’s formula is shown by its asymptotic superiority. For example, let us consider two matrices A and B of n*n dimension, where n is a power of two. It can be observed that we can have four submatrices of order n/2 * n/2 from A, B, and their product C where C is the resultant matrix of A and B.

The procedure of Strassen’s matrix multiplication

Here is the procedure :

Divide a matrix of the order of 2*2 recursively until we get the matrix of order 2*2.
To carry out the multiplication of the 2*2 matrix, use the previous set of formulas.
Subtraction is also performed within these eight multiplications and four additions.
To find the final product or final matrix combine the result of two matrixes.

Formulas for Strassen’s matrix multiplication.

Following are the formulae that are to be used for matrix multiplication.

D1 = (a11 + a22) * (b11 + b22)
D2 = (a21 + a22)*b11
D3 = (b12 – b22)*a11
D4 = (b21 – b11)*a22
D5 = (a11 + a12)*b22
D6 = (a21 – a11) * (b11 + b12)
D7 = (a12 – a22) * (b21 + b22)

C00= d1 + d4 – d5 + d7

C01 = d3 + d5

C10 = d2 + d4

C11 = d1 + d3 – d2 – d6

Here, C00, C01, C10, and C11 are the elements of the 2*2 matrix.

Algorithm for Strassen’s matrix multiplication

The algorithm for Strassen’s matrix Multiplication is as follows:

Algorithm Strass(n, x, y, z)


begin 
If n = threshold then compute
C = x * y is a conventional matrix.
Else
Partition a into four sub matrices  a00, a01, a10, a11.
Partition b into four sub matrices b00, b01, b10, b11.
Strass ( n/2, a00 + a11, b00 + b11, d1)
Strass ( n/2, a10 + a11, b00, d2)
Strass ( n/2, a00, b01 – b11, d3)
Strass ( n/2, a11, b10 – b00, d4)
Strass ( n/2, a00 + a01, b11, d5)
Strass (n/2, a10 – a00, b00 + b11, d6)
Strass (n/2, a01 – a11, b10 + b11, d7)

C = d1+d4-d5+d7       d3+d5
      d2+d4                    d1+d3-d2-d6  

end if
           return (C)
end.

#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;
          // Here we are scanning and printing the first matrix
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]);
            // Here we are scanning and printing the second matrix
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]);
}
          // Here we are applying the above mentioned formulae
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;
          // As we got the value of the elements, we now print them
printf("\n After performing multiplication \n");
for(i=0;i<2;i++){
printf("\n");
for(j=0;j<2;j++)
printf("%d\t",c[i][j]);
}

return 0;
}