Fastest way of multiplying two $n×n$ matrices for fixed $n=1,2,3,\ldots$?

Question

While the question of what is the asymptotically fastest matrix multiplication algorithm is still open, and tremendous improvements were made between 1968 and 1990 (Strassen, Coppersmith-Winograd), I was wondering in the opposite direction, whether it is known what the fastest matrix multiplication algorithm is for matrices of fixed size $n=1,2,3,\ldots$

More specifically, given fixed costs for basic scalar operations, is there some table out there on the web containing this data? How do these algorithms look like for, say, $n=1\ldots 20$? What is smallest $n$ for which the answer is unknown? (I suspect it will be rather small due to combinatorial explosion issues.)

Answer 1

My answer won't answer your entire question, but it will provide a table (well, actually a graph) that shows the elapsed time (ET) for 4 matrix multiplication algorithms when N = 2,...,20.

Before I give this graph, I should underline that this graph only shows the ET of computation. As you may know, there is no direct translation between the ET of computation and the number of arithmetic operations performed by an ALU. Also, I used a Mac to obtain this graph, so nothing fancy. Thus, you may obtain different (lower or higher) ET values on different computers, but the ratio between each algorithm for a given N should remain the same. Also, don't forget that making this test on a regular computer is not the best idea since kernel operations, etc. will/may use the same CPU. Hence, cause a delay here and there.

To obtain this graph, I ran all 4 algorithms over 1e4 realizations for each N and then averaged the results. The first thing you will notice is that the naive method is just... well, naive? Then, Bini's method is somewhere between naive and the others. However, the moment that we reach Strassen's 2nd algorithm, it looks almost like a flat line in linear scale! Hence, you can find the logarithmic y scale in the image below.

Again, naive and Bini seem to keep increasing more than the other two. However, the difference between Strassen-2 and Williams is obvious now. Moreover, you can notice that when we use one of the faster algorithms (Strassen-2 or Williams), there are some small deviations i.e, curves are not as smooth as the others (even though I used 1e4 realizations for averaging). This is simply because we are dealing with such small-time values (small for a regular CPU), the time that it takes to finish an algorithm may deviate between each run.