25 Apr 2024 | Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
This paper presents a new improvement on the laser method for designing fast matrix multiplication algorithms. The method builds upon recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024], achieving a new bound on the square matrix multiplication exponent, ω < 2.371339, improving from the previous bound of ω < 2.371552. The improvement is achieved by incorporating more asymmetry in the analysis, circumventing a fundamental tool of prior work that requires two of the three dimensions to be treated identically. The method also improves bounds for rectangular matrix multiplication exponents, such as ω(1,k,1), which is the smallest real value for which n×k by k×n matrix multiplication can be done in O(n^{ω(1,k,1)+ε}) time for all ε > 0. The paper also provides a detailed overview of the laser method and its application to the Coppersmith-Winograd tensor, showing how asymmetry can be used to improve the algorithm. The results are summarized in Table 1, which compares the new bounds with previous ones. The paper also discusses the limitations of the techniques used and the challenges in solving the non-convex optimization problem required to determine the best choice of the probability distribution for the laser method. The new approach allows for more asymmetry in the algorithm, leading to improved bounds on the matrix multiplication exponent.This paper presents a new improvement on the laser method for designing fast matrix multiplication algorithms. The method builds upon recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024], achieving a new bound on the square matrix multiplication exponent, ω < 2.371339, improving from the previous bound of ω < 2.371552. The improvement is achieved by incorporating more asymmetry in the analysis, circumventing a fundamental tool of prior work that requires two of the three dimensions to be treated identically. The method also improves bounds for rectangular matrix multiplication exponents, such as ω(1,k,1), which is the smallest real value for which n×k by k×n matrix multiplication can be done in O(n^{ω(1,k,1)+ε}) time for all ε > 0. The paper also provides a detailed overview of the laser method and its application to the Coppersmith-Winograd tensor, showing how asymmetry can be used to improve the algorithm. The results are summarized in Table 1, which compares the new bounds with previous ones. The paper also discusses the limitations of the techniques used and the challenges in solving the non-convex optimization problem required to determine the best choice of the probability distribution for the laser method. The new approach allows for more asymmetry in the algorithm, leading to improved bounds on the matrix multiplication exponent.