Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been reading Introduction to Algorithms by Cormen et al. Before explaining Strassen algorithm the book says this:

Strassen’s algorithm is not at all obvious. (This might be the biggest understatement in this book.)

The book just states the algorithm but don't explain why it works. So if we take the case of multiplication of two $2 \times 2$ matrices, it reduces the number of multiplications from $8$ to $7$ thereby reducing the complexity from $n^{3}$ to $n^{\lg 7}$ which is roughly $n^{2.8}$.

My question is why $7$ and say not $5$ or even lesser number? I mean they could have made the recursion tree even less "bushier".

share|improve this question
9  
You are more than welcome to try and come up with an algorithm that only needs $O(n^{\log_25})$ multiplications. –  Jyrki Lahtonen Aug 3 '12 at 17:09
3  
...and if you manage to do so, that'd certainly be journal-worthy. –  J. M. Aug 3 '12 at 17:14
    
$O(n^{2.3727})$ seems to be the best known solution at the moment (google.com/…). These algorithms, opposed to Strassen, only pay of for very, very large matrices far beyond practical use. –  Hauke Strasdat Aug 3 '12 at 17:33
add comment

1 Answer

up vote 13 down vote accepted

Allow me to shamelessly copy an answer of mine to this question first.

The idea behind Strassen multiplication is the same as the idea behind Karatsuba multiplication.

In this, if we have two numbers and a base $B$ (maybe $10^6$, say), and the numbers are written $a = x_0B + x_1$, $b = y_0B + y_1$, and we want to calculate $ab$, then naively we might say that it's

$ab = x_0 y_0 B^2 + (x_0 y_1 + x_1 y_0)B + x_1 y_1 \qquad$ (requiring 4 multiplications)

But we can be wittier, as $x_0y_1 + x_1y_0 = (x_0 + x_1)(y_0 + y_1) - x_0y_0 - x_1y_1 $

So we can calculate $ab$ by knowing $x_0y_0, x_1y_1$ and $(x_0 + x_1)(y_0 + y_1)$, which only uses 3 multiplications. This is just a slick idea, akin to the many other slick arithmetic tricks out there that might be found by inspection, and it became popular in the 1960s. (There's a good story behind it - Karatsuba responded to a challenge of Kolmogorov, ultimately culminating with Kolmogorov writing a paper in Karatsuba's name).

For matrices, a direct port of Karatsuba doesn't quite work. But it's easy to verify that Strassen is true (just write it out). But it's very unclear how Strassen came across them. But it should be mentioned that Strassen was working on many numerical-methods style techniques to improve matrix calculations. It should also be mentioned that Strassen has an improved algorithm, better than this technique, using fast fourier transforms as well.

One might ask: well, we can do it with 7 multiplications. Can we do it with 6? Strassen multiplication has been around since 1969, so surely it's known? This was an open problem until just a few years ago, when Landsberg showed that 7 is optimal. It's nontrivial and a bit far afield for me, but his (corrected after it was published) article can be found on the arXiv.

One might also wonder about $3 \times 3$ matrices. How few multiplications are necessary? Naively, it takes 27 multiplications. But it can be done in 23. (See Julian D. Laderman, A noncommutative algorithm for multiplying 3×3 matrices using 23 muliplications, Bull. Amer. Math. Soc. 82 (1976) 126–128, MR0395320 (52 #16117).) Is that optimal? That's unknown - all that's known is that it takes at least 19. (But if you're just interested in computational savings, even 19 gives less savings when iterated than the $2 \times 2$ case).

So in short, $7$ is optimal. It's not obvious that it's optimal. It was a very clever idea, even, to find the $7$.

share|improve this answer
4  
As commented in the article, it was known that 7 "essential multiplications" are necessary already in 1971 (two years after Strassen's original 1969 paper), and a simple proof appears in Algebraic Complexity Theory. Landsberg proved that the border rank is 7. –  Yuval Filmus Aug 3 '12 at 20:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.