Improving the Leading Constant of Matrix Multiplication

Algebraic matrix multiplication algorithms are designed by bounding the rank of matrix multiplication tensors, and then using a recursive method. However, designing algorithms in this way quickly leads to large constant factors: if one proves that the tensor for multiplying n × n matrices has rank ≤ t, then the resulting recurrence shows that M ×M matrices can be multiplied using O(n 2 •M log n t ) operations, where the leading constant scales proportionally to n 2 . Even modest increases in n can blow up the leading constant too much to be worth the slight decrease in the exponent of M . Meanwhile, the asymptotically best algorithms use very large n, such that n 2 is larger than the number of atoms in the visible universe!

In this paper, we give new ways to use tensor rank bounds to design matrix multiplication algorithms, which lead to smaller leading constants than the standard recursive method. Our main result shows that, if the tensor for multiplying n × n matrices has rank ≤ t, then M × M matrices can be multiplied using only n O(1/(log n) 0.33 ) • M log n t operations. In other words, we improve the leading constant in general from O(n 2 ) to n O(1/(log n) 0.33 ) < n o(1) .

We then apply this and further improve the leading constant in a number of situations of interest. We show that, in the popularly-conjectured case where ω = 2, a new, different recursive approach can lead to an improvement. We also show that the leading constant of the current asymptotically fastest matrix multiplication algorithm, and any algorithm designed using the group-theoretic method, can be further improved by taking advantage of additional structure of the underlying tensor identities.

Our algorithms use new ways to manipulate linear transforms defined by Kronecker powers of matrices, as well as a new algorithm for very rectangular matrix multiplication. In many cases, we entirely avoid applying a large tensor rank identity by instead manipulating it implicitly or decomposing it into smaller, more manageable tensors.