[Lowerbounds, Upperbounds]

Strassen’s algorithm for matrix multiplication is a classic example of how a straightforward algorithm may be beaten asymptotically by a witty one. But there is a problem if you use this example in teaching—how did Strassen come up with the seven intermediate submatrix products?

If you dig up Strassen’s 1969 paper, you’ll see that he didn’t give us any hint. Others have attempted to offer plausible explanations, and you can find one in CLR(S), or a similar and apparently earlier one by Brent on the web.

Now I don’t know about you, but I was never quite convinced when I was reading CLR as a student. But the real kicker comes when later on you were told that Victor Pan has a way to multiply two 70-by-70 matrices with 143640 multiplications… Seventy!?

So I decided to come up with a fairy tale to explain this magical number. But as it turns out, there is not much need for my creativity.

In fact, back in 1984, Victor published a monograph that contains all the glory details that lead to his algorithm. Basically, he designed a class of matrix multiplication algorithms which is parameterized by the size of the submatrices used in the recursion. The number of multiplication happens to be minimized when the submatrices are chosen to be 70 times smaller. It’s just that. No fairy tale is necessary.

Incidentally, the first chapter of his book is more or less available in an article appeared in SIAM Review. You can see page 6 on which he talks about it.

I notice that my neck and wrists suffer quite a bit more during the summer than any other time of the year, even rotating among all sorts of input devices. The reason is quite simple: during the “summer break”, I tend to work longer hours. (That’s quite a “break”, isn’t it? )

Take last Thursday July 6th as an example. It’s one day after the SODA deadline, so it is a “good” day. On my primary work machine, I typed from 09:17 to 00:58, making 36676 keystrokes. The mouse was in use for 1:23, moving a distance of 415 meters while clicking 3258 times.

But where do I get all these numbers? Workrave.

Workrave is a program that assists in the recovery and prevention of Repetitive Strain Injury (RSI). The program frequently alerts you to take micro-pauses, rest breaks and restricts you to your daily limit. […] The program runs on GNU/Linux and Microsoft Windows.

Besides its micro-break feature, I consider the statistics it collects to be very valuable. Think about all kinds of charts you can plot…