A Refined Laser Method and Faster Matrix Multiplication

Abstract

The complexity of matrix multiplication is measured in terms of $\omega$, the smallest real number such that two $n\times n$ matrices can be multiplied using $O(n^{\omega +\epsilon })$ field operations for all $\epsilon >0$; the best bound until now is $\omega <2.37287$ [Le Gall'14]. All bounds on $\omega$ since 1986 have been obtained using the so-called laser method, a way to lower-bound the `value' of a tensor in designing matrix multiplication algorithms. The main result of this paper is a refinement of the laser method that improves the resulting value bound for most sufficiently large tensors. Thus, even before computing any specific values, it is clear that we achieve an improved bound on $\omega$, and we indeed obtain the best bound on $\omega$ to date: $$\omega <\mathrm{2.37286.}$$ The improvement is of the same magnitude as the improvement that [Le Gall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvement to the laser method is quite general, and we believe it will have further applications in arithmetic complexity.

32 pages; TheoretiCS journal version

References in corpus (1)

• On cap sets and the group-theoretic approach to matrix multiplication

Cited by in corpus (10)

• ThinCurr: An open-source 3D thin-wall eddy current modeling code for the analysis of large-scale systems of conducting structures
• Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths
• The Cost of Compositionality: A High-Performance Implementation of String Diagram Composition
• Quantum algorithm for solving generalized eigenvalue problems with application to the Schrödinger equation
• Explicit Riemann-Roch spaces in the Hilbert class field
• Computing the Characteristic Polynomial of Generic Toeplitz-like and Hankel-like Matrices
• The Complexity of Checking Partial Total Positivity
• Instance Based Approximations to Profile Maximum Likelihood
• Benchmarking quantum devices beyond classical capabilities
• Optimal Structured Matrix Approximation for Robustness to Incomplete Biosequence Data