New Bounds for Matrix Multiplication: from Alpha to Omega
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou
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 ω, but also improve the known bounds on rectangular matrix multiplication by [Le Gall and Urrutia, SODA 2018].
Topics & Concepts
ExponentMatrix multiplicationMultiplication (music)MathematicsMatrix (chemical analysis)OmegaCombinatoricsUpper and lower boundsArithmeticDiscrete mathematicsMathematical analysisPhysicsChemistryQuantum mechanicsPhilosophyQuantumChromatographyLinguisticsCoding theory and cryptographyQuantum Computing Algorithms and ArchitectureTensor decomposition and applications