Suppose you want to multiply two 2 × 2 matrices together. How many multiplication operations does it take? Apparently 8, and yet in 1969 Volker Strassen discovered that he could do it with 7 multiplications.
Upper and lower bounds
The obvious way to multiply two n × n matrices takes n³ operations: each entry in the product is the inner product of a row from the first matrix and a column from the second matrix. That amounts to n² inner products, each requiring n multiplications.
You can multiply two square matrices with O(n³) operations with the method described above, and it must take at least O(n²) operations because the product depends on all of the 2n² entries of the two matrices. Strassen’s result suggests that the optimal algorithm for multiplying matrices takes O(nk) operations for some k between 2 and 3. By applying Strassen’s algorithm recursively to larger matrices you can get k = log2 7 = 2.807.
The best known value at the moment is k = 2.3728639.
Bounds on bounds
Yesterday the blog Gödel’s Lost Letter and P = NP posted an article Limits on Matrix Multiplication where they report on recent developments for finding the smallest value of k. A new paper doesn’t report a new value of k, but a limit on what current approaches to the problem can prove. Maybe k can equal 2, but there is a lower bound, strictly bigger than 2, on how small current approaches can go.
Is this practical?
When I first heard of Strassen’s method, I was told it’s a curious but impractical result. Strassen saved one multiplication at the expense of introducing several more addition operations.
According to the Wikipedia article on matrix multiplication, recursively applying Strassen’s method can save time for n > 100. But there’s more to consider than counting operations. Strassen’s method, and subsequent algorithms, are more complicated. They may not be more efficient in practice even if they use fewer operations because the operations may not vectorize well.
Wikipedia reports that Strassen’s algorithm is not as numerically stable as the traditional approach, but this doesn’t matter when working over finite fields where arithmetic is exact.
Strassen’s method
Let’s look at just what Strassen’s method does. We want to find the product of two matrices:
I started to spell out Strassen’s method in LaTeX equations, but I thought it would be much better to write it out in code so I can be sure that I didn’t make a mistake.
The following Python code randomly fills in the values of the a’s and b’s, computes the c’s using the conventional method, then asserts that you can find these values from the q’s computed from Strassen’s method. Note there is one multiplication in each of the seven q’s.
from random import randint
# Fill matrices with random integer values
a11 = randint(0, 9)
a12 = randint(0, 9)
a21 = randint(0, 9)
a22 = randint(0, 9)
b11 = randint(0, 9)
b12 = randint(0, 9)
b21 = randint(0, 9)
b22 = randint(0, 9)
# Traditional matrix multiplication
c11 = a11*b11 + a12*b21
c12 = a11*b12 + a12*b22
c21 = a21*b11 + a22*b21
c22 = a21*b12 + a22*b22
# Strassen's method
q1 = (a11 + a22)*(b11 + b22)
q2 = (a21 + a22)*b11
q3 = a11*(b12 - b22)
q4 = a22 * (-b11 + b21)
q5 = (a11 + a12)*b22
q6 = (-a11 + a21)*(b11 + b12)
q7 = (a12 - a22)*(b21 + b22)
assert(c11 == q1 + q4 - q5 + q7)
assert(c21 == q2 + q4)
assert(c12 == q3 + q5)
assert(c22 == q1 + q3 - q2 + q6)
Since Strassen’s method takes more operations than the traditional method for multiplying 2 × 2 matrices, how can it take fewer operations than the traditional method for multiplying large matrices?
When you apply Strassen’s method to a matrix partitioned into submatrices, its multiplications become matrix multiplications, and its additions become matrix additions. These operations are O(n2.807) and O(n2) respectively, so saving multiplications at the cost of more additions is a win.
The asymmetry of the formula is interesting. Suppose you knew ahead of time that one of the matrix entries was zero. You can reduce the naive formula to 6 multiplications using this fact, but the Strassen formula only reduces to 6 multiplications if the zero entry is on the diagonal. If it’s on the off diagonal, you still get 7 multiplications.