Strassen's algorithm for matrix multiplication

algorithm matrix multiplication strassen
confused_by_strassen picture confused_by_strassen · Dec 17, 2009 · Viewed 25.4k times · Source

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

Keith Randall picture Keith Randall · Dec 17, 2009

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.

Related questions

Divide and Conquer Matrix Multiplication

I am having trouble getting divide and conquer matrix multiplication to work. From what I understand, you split the matrices of size nxn into quadrants (each quadrant is n/2) and then you do: C11 = A11⋅ B11 + A12 ⋅ B21 C12 = A11⋅ …

Read More
How do you rotate a two dimensional array?

Inspired by Raymond Chen's post, say you have a 4x4 two dimensional array, write a function that rotates it 90 degrees. Raymond links to a solution in pseudo code, but I'd like to see some real world stuff. [1][2][3][4] [5][6][7][8] [9][0][1][2] [3][4][5][6] Becomes: [3][9][5][1] [4][0][6][2] [5][1][7][3] [6][2][8][4] Update: Nick's …

Read More
Python Inverse of a Matrix

How do I get the inverse of a matrix in python? I've implemented it myself, but it's pure python, and I suspect there are faster modules out there to do it.

Read More