What constant in the latest fast matrix multiplication is hidden by Big-O notation?

Question

I'm evaluating the theoretical run time of matrix multiplication algorithms as it has improved within the last few decades. Algorithms to solve matrix multiplication run in O(n^w) time, where w has evolved in the following way:

• w = 3 if using a brute-force approach,
• w = 2.8074 if using Volker Strassen's algorithm [1969],
• ... (some interesting improvements later :))
• w = 2.3729 if using Virginia Vassilevska-Williams analysis of the Coppersmith–Winograd algorithm [2011]
• w = 2.3728639 if using François Le Gall's adaptation of the Coppersmith–Winograd algorithm [2014]

I often hear that the more recent algorithms presented, while theoretically interesting since w approaches 2, are not practical due to the large constant hidden by Big-O. In other words, that the size of the input matrix would need to be extremely large in order for it to be an improvement over Strassen's algorithm, for example. I would like to put a number to this.

What is the rough value of this hidden constant for any of the more recent fast matrix multiplication algorithms? Or, for roughly what input size n of a matrix would the fast matrix multiplication algorithm use less operations than Strassen's algorithm, or the brute force approach?

Answer 1

All improvements since Strassen's original algorithm only achieve their exponent in the limit. That is, if they are stated as $O(n^c)$ algorithms, what they really show is that for every $\epsilon>0$ you can multiply two $n\times n$ matrices using at most $C_\epsilon n^{c-\epsilon}$ multiplications, where the constant $C_\epsilon$ blows up badly (exponentially in $1/\epsilon$?) as $\epsilon\to0$. (Coppersmith and Winograd showed that this kind of behavior is actually necessary.)

The papers don't explicitly compute $C_\epsilon$. One reason is that if you are serious about the constant, then you will probably need to apply low-level optimizations that will improve $C_\epsilon$ at the expense of the simplicity of the algorithm. Another reason is that due to the exponential dependence on $1/\epsilon$, you don't expect the result to be practically meaningful, so it's not really worth it. A third reason is that fast matrix multiplication algorithms are developed in a more abstract framework, which makes it awkward to come up with an actual explicit algorithm.

Fast matrix multiplication algorithms are recursive, that is, they iterate a smart $m\times m$ multiplication algorithm. Whereas for Strassen's original algorithm $m = 2$, for the improvements $m$ depends on $\epsilon$ (exponentially?), and so you will only be able to apply the base case for very large matrices; and for such large matrices, you would actually do much worse than the high school algorithm. The benefits of these algorithms only show up once they have been iterated many times, which would correspond to astronomically high (or worse) dimensions.

If you do feel like working out a constant, there are several expositions of the theory of fast matrix multiplication. You could take the first improvement over Strassen's original algorithm, and try to work out what the parameters are like.

Answer 2

You need to know what you are up against. I assume that you compare one of the "fast" algorithms against an efficient implementation of either naive matrix multiplication or Strassen's 1969 algorithm (it seems that Strassen created an algorithm in 1986 that formed the basic of Coppersmith-Winograd and others).

While the number of multiplications and additions in the naive algorithm is very easy to calculate, the time it takes is much more complicated.

The first problem is that a naive implementation will take most of its time reading the same matrix elements again and again. So the first step is to rearrange the operations so that we read the same numbers again and again. For example, we split the matrices into blocks of 80x80 items or however many fit into the fastest cache. If done properly, this leads to every number being read 80 times from the fastest cache for each time it is read from slower memory.

The next problem is latency. If we naively add up a sum of products, where each addition relies on the result of the previous one, we are limited by the speed of an addition. Instead we calculate multiple sums in parallel, so we are only limited by the number of additions that can be done in parallel.

Then we would use vector instructions. Modern processors may be able to do 4 additions in one instruction as fast as a single one. And then we have to try to use multiple processors that may be available. So with a perfect implementation, the total runtime might be one cycle per four multiplications per available processor.

For large n, say n ≥ 1000, Strassen's method is perfectly efficient. However, it doesn't gain much. If you multiply n by 1000, the number of multiplications grows by 264 millions instead of 1000 millions. Absolutely worthwhile but the gain is not that much.

If you examine a faster algorithm, you really need to examine an implementation. And you can assume that the implementation has been done very carefully to gain the maximum speed, because otherwise what is the point?

So you need to check: How many multiplications and additions are needed? And how many can be performed per cycle? For example, if your algorithm addresses items with no simple pattern, just reading a value might take 100 times longer than a multiplication.