New Bounds for Matrix Multiplication: from Alpha to Omega
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou · Society for Industrial and Applied Mathematics eBooks · 2024
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].