New Bounds for Matrix Multiplication: from Alpha to Omega

The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu, Zhou, FOCS 2023], the new method introduces several new ingredients that not only yield an improved bound on the matrix multiplication exponent ω, but also improve the known bounds on rectangular matrix multiplication by [Le Gall and Urrutia, SODA 2018].

In particular, the new bound on ω is ω ≤ 2.371552 (improved from ω ≤ 2.371866).

For the dual matrix multiplication exponent α defined as the largest α for which ω(1, α, 1) = 2, we obtain the improvement α ≥ 0.321334 (improved from α ≥ 0.31389).

Similar improvements are obtained for various other exponents for multiplying rectangular matrices.