# Strassen Multiplication?

How are the values of the 7 new matrices derived? I'm referring to the values that reduce matrix multiplication to 7 multiplications per level:

$M_1 = \left(A_{1,1} + A_{2,2}\right)\left(B_{1,1} + B_{2,2}\right)$

...

$M_7 = \left(A_{1,2} - A_{2,2}\right)\left(B_{2,1} + B_{2,2}\right)$

Could someone show how these values were arrived at?

-
I don't know the details here, but I suppose it's just a generalization of Karatsuba's approach to matrices. – Johannes Kloos May 11 '12 at 17:00
The idea is similar to divide and conquer where you work on sub-problems (sub-matrices in this case) and try to get the answer for the actual problem by putting together information from the sub-problems in an effective way. "How these matrices were arrived at?" is a difficult question to answer. It relies on a trick and how to efficiently reuse information so that the $8$ products can be obtained from just $7$ products. (though "nothing is a trick if seen from a sufficiently high level" quoting Qiaochu Yuan. Just that I am unable to explain the trick in simple terms.) – user17762 May 11 '12 at 17:11
It is analogous to computing product of complex numbers i.e. $(a+ib)(c+id) = (ac-bd)+i(ad+bc)$ which seems to require $4$ multiplication but you can actually get away with $3$ namely $(a+b)(c+d)$, $ac$ and $bd$ since $(ad+bc) = (a+b)(c+d) - ac -bd$. – user17762 May 11 '12 at 17:11
@user26649: A link would be nice, so that we know what you're talking about. – TonyK May 5 '15 at 18:07

## 2 Answers

As Johannes Kloos indicated in the comments, 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).

-
Thanks, that helped! – user26649 May 12 '12 at 0:26
It is interesting that the same answer gets a completely different reaction when posted at a different moment in time. Maybe the long quote block helped. Who knows? :) Nice answer anyway. – t.b. Aug 4 '12 at 16:28
@t.b. It's all a big mystery to me too. I think you were my 20k vote, too. Thank you - – mixedmath Aug 4 '12 at 17:01
Oh, sure... As Alex Bartel said somewhere: worrying over votes will only result in your losing your hair -- or something like that. Welcome to the trusted club! See you around. – t.b. Aug 4 '12 at 17:06
(1) Hopcroft & Kerr and (independently) Winograd showed already in 1971 that 7 multiplications are required. Landsberg showed (roughly) that 7 multiplications are required even if you only want to "estimate" the answer, in some sense. (2) Strassen's improved algorithm using FFT, usually known as Solovay-Strassen, is for integer multiplication, and has been improved by Fürer. (3) The asymptotically fastest matrix multiplication algorithm known at present is due to Le Gall. – Yuval Filmus May 5 '15 at 18:08

You can check out a derivation in the following blog:

http://jacobminz.blogspot.in/2015/05/derivation-of-strassens-algorithm-for.html

I'm not so sure that Karatsuba's method may be modified to derive Strassen's algorithm, because polynomial multiplications and matrix multiplications are very different problems. Of course, there is a possibility that I may be wrong as well.

-
I wouldn't say the derivation. At most it's a derivation. – Yuval Filmus May 5 '15 at 18:09
Ok got it. Hopefully it is a correct and easy to understand derivation. Thanks. – Jacob Minz May 5 '15 at 18:49