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, • 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, ### Example of 4×4 Strassen’s matrix

Consider a matrix which is of order 4×4, we need to find its multiplication. To solve & multiply these matrices we need to follow some steps,

Step 1: Firstly divide A & B into 4 sub equivalent parts. 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  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 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, So here, Now for C2, take consider the matrix A2 & B2

We know C2 = 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, So, C2 becomes, For C3, We have to consider A3 & B3 and implement it in the form of C3=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, So, C3 becomes Finally we need to find C4 which will be equivalent to C4=A4.B4

So consider 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, Finally C4 will be equal to, PLEASE COME BACK 😊