More Asymmetry Yields Faster Matrix Multiplication

More Asymmetry Yields Faster Matrix Multiplication

25 Apr 2024 | Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
The paper presents a new improvement to the laser method for designing fast matrix multiplication algorithms. This improvement incorporates more asymmetry in the analysis, overcoming a fundamental limitation of prior work that required treating two of the three dimensions identically. The new method yields an improved bound on the square matrix multiplication exponent: \[ \omega < 2.371339, \] which is an improvement over the previous bound of \(\omega < 2.371552\). The method also improves bounds on the exponents for multiplying rectangular matrices of various shapes. The key contribution is a new approach that allows different remaining subtensors to share level-\(\ell\) variable blocks in both the \(Y\) and \(Z\) dimensions, while still requiring them to be independent with respect to level-1 blocks. This introduces more asymmetry, which helps to overcome limitations in the previous methods. The paper discusses the technical details of the laser method, including the use of complete split distributions and the analysis of the Coppersmith-Winograd tensor.The paper presents a new improvement to the laser method for designing fast matrix multiplication algorithms. This improvement incorporates more asymmetry in the analysis, overcoming a fundamental limitation of prior work that required treating two of the three dimensions identically. The new method yields an improved bound on the square matrix multiplication exponent: \[ \omega < 2.371339, \] which is an improvement over the previous bound of \(\omega < 2.371552\). The method also improves bounds on the exponents for multiplying rectangular matrices of various shapes. The key contribution is a new approach that allows different remaining subtensors to share level-\(\ell\) variable blocks in both the \(Y\) and \(Z\) dimensions, while still requiring them to be independent with respect to level-1 blocks. This introduces more asymmetry, which helps to overcome limitations in the previous methods. The paper discusses the technical details of the laser method, including the use of complete split distributions and the analysis of the Coppersmith-Winograd tensor.
Reach us at info@study.space