Strassen's algorithm for multiplication of n*n matrices.

Strassen proposed a method that allows us to find the product of two n*n matrices more quickly than the standard multiplication method.

Why was this so crucial??

Because in the standard multiplication approach and using the simple divide and conquer method, the time complexity is calculated as follows:

Standard Multiplication Method:

T(n)=O(n^3)        

Simple Divide & Conquer Method:

 T(n) ≤?8*T(n/2) + O(n^2)
 
∴T(n) = n^(ln 8)
 T(n) = n^3        

Using the simple divide-and-conquer strategy, we must compute eight distinct products and then sum them to arrive at the final solution.

What did Strassen do?

Strassen discovered a method for successfully computing the product of two matrices using only seven distinct products. Eliminating a single product dramatically reduced time complexity and improved the process.

Only these seven products of sub-matrices are required:

p1=a*(f-h)
p2=(a+b)*h
p3=(c+d)*h
p4=d*(g-e)
p5=(a+d)*(e+h)
p6=(b-d)*(g+h)
p7=(a-c)*(e+f)        

Strassen computed the final outcome as follows:

Thus, reducing time complexity to:

T(n) ≤?7*T(n/2) + O(n^2)
 
∴T(n) = n^(ln 7)
 T(n) = n^2.80735