Today I Learned: the Strassen Algorithm

There's a reason why most of us are taught addition before multiplication - it's just so much easier (*). And so, it was pretty big deal when people invented Logarithms, because the fact that \begin{align}\log(xy)=\log(x)+\log(y)\end{align} meant that (provided that you could convert from a number \(x\) into its logarithm \(\log(x)\)) you were able to covert a multiplication problem into an addition one.

Now, I must admit that I was super-surprised to find out that the first (proper) logarithm ever developed was (more-or-less) done in base \(1-10^{-7}\). It...just seemed sooooooo arbitrary! Though, I think that there's probably a good astronomy-based explanation for why this base was chosen (**)... in fact, I might've even heard this explained on one of the recent episodes of the BBC In Our Time podcast? (hint: you should totes go check it out =P)

Analogously, matrix multiplication is also harder than matrix addition. And the fact that even for \(2\times2\) matrices, matrix multiplication \begin{align} \left[\begin{array}{c}{c} a_{11} & a_{12} \\ a_{21} & a_{22}\end{array}\right] \left[\begin{array}{c}{c} b_{11} & b_{12} \\ b_{21} & b_{22}\end{array}\right] = \left[\begin{array}{c}{c} a_{11}\times b_{11}+a_{12}\times b_{21} & a_{11}\times b_{12}+a_{12}\times b_{22} \\ a_{21}\times b_{11}+a_{22}\times b_{21} & a_{21}\times b_{12}+a_{22}\times b_{22}\end{array}\right] \end{align} actually requires 8 little multiplications just adds insult to injury...ammirite?

Weeeeell, fear no more! Because we can totally reduce \(2\times2\) matrix multiplication down to just 7 multiplications (***)! And here's how:

Start by computing these guys:

1. \(m_1:=(a_{11}+a_{22})\times (b_{11}+b_{22})\),
2. \(m_2:=(a_{21}+a_{22})\times b_{11}\),
3. \(m_3:=a_{11}\times (b_{12}- b_{22})\),
4. \(m_4:=a_{22}\times (b_{21}-b_{11})\),
5. \(m_5:=(a_{11}+a_{12})\times b_{22}\),
6. \(m_6:=(a_{21}-a_{11})\times (b_{11}+b_{12})\),
7. \(m_7:=(a_{12}-a_{22})\times (b_{21}+b_{22})\).

This takes up all 7 of the multiplications that we're allowing ourselves. To finish off the matrix multiplication, the four entries of our multiplied matrix are given by:

1. \(m_1+m_4-m_5+m7\),
2. \(m_3+m_5\),
3. \(m_2+m_4\),
4. \(m_1-m_2+m_3+m_6\).

Et voila! THIS is called the Strassen Algorithm.

Now, this might seem like kind of a stupid thing to do, but I think that it was supposedly kinda useful in the early days of computing, i.e.: when computers had trouble handling multiplication. Just...umm...goes to show, right? Multiplication...so much harder than addition. =P

 *: unless if you're dealing with \(0\)...in which case, it's pretty easy either way
**: coupled with the fact that \((1-10^{-7})^{10^7}\approx\frac{1}{e}\)
***: but with a few more additions, which is fine, because additions are totally easier than multiplications