Strassen's algorithm for matrix multiplication

Question

Can someone please explain strassen's algorithm for matrix multiplication in an intuitive way? I've gone through (well, tried to go through) the explanation in the book and wiki but it's not clicking upstairs. Any links on the web that use a lot of English rather than formal notation etc. would be helpful, too. Are there any analogies which might help me build this algorithm from scratch without having to memorize it?

Answer 1

Consider multiplying two 2x2 matrices, as follows:

A B * E F = AE+BG AF+BH C D   G H   CE+DG CF+DH 

The obvious way to compute the right side is just to do the 8 multiplies and 4 additions. But imagine multiplies are a lot more expensive than additions, so we want to reduce the number of multiplications if at all possible. Strassen uses a trick to compute the right hand side with one less multiply and a lot more additions (and some subtractions).

Here are the 7 multiplies:

M1 = (A + D) * (E + H) = AE + AH + DE + DH M2 = (A + B) * H = AH + BH M3 = (C + D) * E = CE + DE M4 = A * (F - H) = AF - AH M5 = D * (G - E) = DG - DE M6 = (C - A) * (E + F) = CE + CF - AE - AF M7 = (B - D) * (G + H) = BG + BH - DG - DH 

So to compute AE+BG, start with M1+M7 (which gets us the AE and BG terms), then add/subtract some of the other Ms until AE+BG is all we are left with. Miraculously, the M's are chosen so that M1+M7-M2+M5 works. Same with the other 3 results required.

Now just realize this works not just for 2x2 matrices, but for any (even) sized matrices where the A..H are submatrices.