8
$\begingroup$

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.)

$\endgroup$
7
  • $\begingroup$ So by “fastest algorithm” you mean the formula with the least number of arithmetic operations? Did you try searching the OEIS? $\endgroup$ Aug 18, 2021 at 21:06
  • $\begingroup$ @JossevanDobbendeBruyn yes I do mean number of arithmetic operations. I suppose some authors will only count multiplications, while others will count both multiplications and additions. $\endgroup$
    – Hyperplane
    Aug 18, 2021 at 23:50
  • 8
    $\begingroup$ For $n=3$, a classic result is by Laderman (1976) that 23 multiplications suffice. And Bläser (2003) showed that at least 19 are needed. See Heule, Kauers & Seidl (2021) for a recent listing of known results: doi.org/10.1016/j.jsc.2020.10.003 $\endgroup$ Aug 19, 2021 at 17:10
  • $\begingroup$ For $n=1$ (i.e. multiplication of numbers) there is an algorithm by Harvey and van der Hoeven (2019) in $O(d\log d)$ where $d$ is the number of digits. It's conjectured that this is best possible. $\endgroup$ Aug 24, 2021 at 12:49
  • 1
    $\begingroup$ I think including $n=1$ is nice. At least you can then start the table with something that is certainly known! $\endgroup$ Aug 25, 2021 at 6:54

1 Answer 1

-1
$\begingroup$

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.

For each N, 1e4 realizations are performed, and the result is averaged.

$\endgroup$
1
  • 3
    $\begingroup$ Sorry, but the question really isn't about wall clock time on a real CPU, but about the complexity theoretic question of how many arithmetic operations are at minimum necessary to perform the computation. $\endgroup$
    – Hyperplane
    Aug 24, 2021 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.