Strassen's matrix multiplication

Strassen's matrix multiplication:

 Following is simple Divide and Conquer method to multiply two square matrices.

1) Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below diagram.

2) Calculate following values recursively. ae + bg, af + bh, ce + dg and cf + dh.

In the above method, we do 8 multiplications for matrices of size N/2 x N/2 and 4 additions. Addition of two matrices takes O(N²) time. So the time complexity can be written as T(N) = 8T(N/2) + O(N2). From Master's Theorem, time complexity of above method is O(N³) . This is same as naive method of matrix multiplication time complexity.

In the above divide and conquer method, the main component for high time complexity is 8 recursive calls. The idea of Strassen’s method is to reduce the number of recursive calls to 7. Strassen’s method is similar to above simple divide and conquer method in the sense that this method also divide matrices to sub-matrices of size N/2 x N/2 as shown in the diagram, but in Strassen’s method, the four sub-matrices of result are calculated using following formulae.

The following are the values of four sub matrices of result C

Time Complexity of Strassen’s Method:
Addition and Subtraction of two matrices takes O(N²) time. So time complexity can be written as

T(N) = 7T(N/2) +  O(N²)

The time complexity of above method is  O(N^Log7) which is approximately O(N^2.8074)