Strassen’s Matrix Multiplication Algorithm

In this context, using Strassen’s Matrix multiplication algorithm, the time consumption can be improved a little bit. Strassen’s Matrix multiplication can be performed only on square matrices where n is a power of 2. Order of both of the matrices is n × n.

Divide X, Y and Z into four (n/2)×(n/2) matrices as represented below −

Z=[IKJL]Z=[IJKL] X=[ACBD]X=[ABCD] and Y=[EGFH]Y=[EFGH]

Using Strassen’s Algorithm computes the following −

M1:=(A+C)×(E+F)

M2:=(B+D)×(G+H)

M3:=(A−D)×(E+H)

M4:=A×(F−H)

M5:=(C+D)×(E)

M6 :=(A+B)×(H)

M7:=D× (G−E)

Then,

I: =M2+M3−M6−M7

J: =M4+M6

K: =M5+M7

Introduction to analysis of algorithm Page | 24

L: =M1−M3−M4−M5

Constants

Using this recurrence relation, we get T(n)=O(nlog7)T(n)=O(nlog7)

Hence, the complexity of Stassen’s matrix multiplication algorithm is O(nlog7)O(nlog7).