References & Citations
Computer Science > Data Structures and Algorithms
Title: New Bounds for Matrix Multiplication: from Alpha to Omega
(Submitted on 16 Jul 2023 (v1), last revised 4 Nov 2023 (this version, v2))
Abstract: 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 $\omega$, but also improve the known bounds on rectangular matrix multiplication by [Le Gall and Urrutia, SODA 2018]. In particular, the new bound on $\omega$ is $\omega\le 2.371552$ (improved from $\omega\le 2.371866$). For the dual matrix multiplication exponent $\alpha$ defined as the largest $\alpha$ for which $\omega(1,\alpha,1)=2$, we obtain the improvement $\alpha \ge 0.321334$ (improved from $\alpha \ge 0.31389$). Similar improvements are obtained for various other exponents for multiplying rectangular matrices.
Submission history
From: Renfei Zhou [view email][v1] Sun, 16 Jul 2023 07:46:06 GMT (57kb)
[v2] Sat, 4 Nov 2023 04:45:36 GMT (57kb)
Link back to: arXiv, form interface, contact.