Important Concepts

Strassen’s matrix multiplication 4×4 example

Strassen’s matrix multiplication method is based on a divide & conquer rule. We have implemented a simple formula for you to find the Strassen’s matrix multiplication of the 4×4 matrix. In this post, I will try to explain the concept of Strassen’s 4×4 matrix multiplication with an example.

Overview of Strassen’s algorithm

  • Strassen’s matrix multiplication will take less time to multiply two matrices using programming as compare to normal matrix multiplication.
  • It is applicable to the matrices of order (n*n).
  • If we have a 4×4 matrix, then we need to divide it into 4 equal parts.

Formula of Strassen’s matrix multiplication

Suppose we have two matrices A & B then the applicable formula is,

2x2 strassen's matrix

  • P1= a * ( f – h )
  • P2 = h * ( a + b )
  • P3 = e * ( c + d )
  • P4 = d * ( g – e )
  • P5 = ( a + d ) * ( e + h )
  • P6 = ( b – d ) * ( g + h )
  • P7 = ( a – c ) * ( e + f )

So the final matrix is,

STRASSEN'S MATRIX MULTIPLICATION

Example of 4×4 Strassen’s matrix

Consider a matrix which is of order 4×4, we need to find its multiplication.

STRASSEN'S MATRIX MULTIPLICATION 4x4

To solve & multiply these matrices we need to follow some steps,

Step 1: Firstly divide A & B into 4 sub equivalent parts.

STRASSEN'S MATRIX MULTIPLICATION division

Step 2: Write this matrix in the form of four 2×2 matrices and name them accordingly like A1, A2, A3, A4, B1, B2, B3, B4

STRASSENS MATRIX

STRASSENS MATRIX MULTIPLICATION

Step 3: Finally we need to find the multiplications of these matrices one by one in such a way that

  • C1 = A1.B1
  • C2 = A2.B2
  • C3 = A3.B3
  • C4 = A4.B4


So for C1, take consider the matrix A1 & B1

We know C1 = A1.B1

strassens matrix 2x2

So,

  • P1= a*(f – h) = 3*(6-3) = 9
  • P2 = h*(a + b) = 3*(3+2) = 15
  • P3 = e*(c + d) =  5*(5+6) = 55
  • P4 = d*(g – e) = 6*(1-5) = -24
  • P5 = (a + d)*(e + h)= (3+6)*(5+3) = 72
  • P6 = (b – d)*(g + h)= (2-6)*(1+3) = -16
  • P7 = (a – c)*(e + f)= (3-5)+(5+6) = -22

We know,

STRASSEN'S MATRIX MULTIPLICATION

So here,

strassens c1


Now for C2, take consider the matrix A2 & B2

We know C2 = A2.B2

strassens a2 b2

Similarly here we have,

  • P1= a * ( f – h ) = 1
  • P2 = h * ( a + b ) = 0
  • P3 = e * ( c + d ) = 63
  • P4 = d * ( g – e ) = -35
  • P5 = ( a + d ) * ( e + h ) = 56
  • P6 = ( b – d ) * ( g + h ) = -14
  • P7 = ( a – c ) * ( e + f ) = -8

Similarly,

STRASSEN'S MATRIX MULTIPLICATION

So, C2 becomes,

strassens c2


For C3, We have to consider A3 & B3 and implement it in the form of C3=A3.B3.

strassens matrix - a3 b3

Now we have to find P1, P2…..P7

  • P1= a * ( f – h ) = 21
  • P2 = h * ( a + b ) = 39
  • P3 = e * ( c + d ) = 15
  • P4 = d * ( g – e ) = -6
  • P5 = ( a + d ) * ( e + h ) = 72
  • P6 = ( b – d ) * ( g + h ) = 20
  • P7 = ( a – c ) * ( e + f ) = 66

Now we have to find C,

STRASSEN'S MATRIX MULTIPLICATION

So, C3 becomes

strassens multiplication c3


Finally we need to find C4 which will be equivalent to C4=A4.B4

So consider A4 & B4

strassens matrix - a4 b4

Finally find P1, P2….P7

  • P1= a * ( f – h ) = 5
  • P2 = h * ( a + b ) = 0
  • P3 = e * ( c + d ) = 56
  • P4 = d * ( g – e ) = 10
  • P5 = ( a + d ) * ( e + h ) = 70
  • P6 = ( b – d ) * ( g + h ) = -27
  • P7 = ( a – c ) * ( e + f ) = 16

Now we have find C,

STRASSEN'S MATRIX MULTIPLICATION

Finally C4 will be equal to,

strassens c4


PLEASE COME BACK 😊


ALSO READ-

-> Algorithm ( A Complete Introduction )

-> Getch() in C

-> String args in Java

Leave a Reply