New constructive proof shows faster matrix multiplication possible
Matrix Multiplication from Polynomial Packings: A Constructive and Elementary Proof of $ω\le9/4$
Computational Complexity
Summary
Matrix multiplication is an important operation in computing, and how quickly it can be done is measured by the exponent ω. The authors provide a clear, step-by-step proof that this exponent is at most 2.25, improving previous results. They build an explicit method based on a known framework and show how to multiply large integer matrices faster than before. This could lead to more efficient algorithms in computer science.
What this means in practice
- •For software engineers: Optimize matrix multiplication libraries using an explicit faster algorithm with improved operation counts.
- •For data scientists: Speed up large-scale numerical computations involving matrix multiplications by leveraging the improved exponent in algorithm design.
A theory result. No direct application yet.
Authors
Rafael Pass
Abstract
We give a self-contained constructive proof that the matrix multiplication exponent satisfies $ω\le9/4$. This bound was recently claimed by OpenAI~\cite{original} through non-constructive arguments in Strassen's asymptotic spectral framework, counting exact scalar arithmetic operations over the complex numbers. We explicitly construct a Strassen-style matrix multiplication identity and obtain the bound by ordinary block recursion. For every $γ>0$, the resulting algorithm multiplies two $n\times n$ integer matrices using $O(n^{9/4+γ})$ integer arithmetic operations.