Strassen's Subcubic Matrix Multiplication Algorithm

A Review on Matrix Multiplication
Given two 2 nxn matrices X, Y and their product matrix Z, we know that Z_ij = (ith row of X) · (jth column of Y). This naive algorithm requires three for loops, two to traverse the Z matrix and one to obtain the values from X and Y for the dot product. This has an overall runtime of O(n³).

If we think back to MergeSort, we can attempt to apply the Divide and Conquer algorithm design paradigm. We can split each matrix into 4 matrices, as such:

A B C D

E F G H

=

AE+BG AF+BH CE+DG  CF+DH

Then, it can be proven that if we split the product matrix in 4 matrices as well, each submatrix will be the product of the corresponding submatrices in the two matrices.

Then to compute this product, we will need to do 8 recursive calls: 4 submatrices with two factors each.   It turns out that this is no better than the naive approach. It also has a runtime of O(n³).

Strassen's algorithm makes it possible to solve the problem with only 7 recursive calls. This may seem like a small decrease but if we do 1/8 less work on each time we recurse, the total amount of work saved is pretty significant. This turns out to have a subcubic runtime. 

The Algorithm So what is the algorithm? We need 7 recursive calls to find 7 products:

P₁ = A(F - H)

P₂ = (A + B)H

P₃ = (C + D)H

P₄ = D(G - E)

P₅ = (A + D)(E + H)

P₆ = (B - D)(G + H)

P₇ = (A - C)(E + F)

Then, it is claimed that

AE+BG  AF+BH CE+DG CF+DH

=

P6+P5+P4-P2 P1+P2 P3+P4 P1-P3+P5-P7

This makes you wonder how in the world did Strassen come up with P₁ through P₇. We have no idea. "How can we make this better?" This is the ultimate question for coming up with better and better algorithms to solve our problems.