Exponent of matrix multiplication complexity
edit on github · preview edits · show history · long url · complexity algorithms matrix multiplication
Number
$\omega$
[2, 2.3728596]
Definition
$\omega$ is the smallest real number such that any two $n\times n$ matrices can be multiplied in $O(n^{\omega+\varepsilon})$ field operations for any $\varepsilon > 0$.
(1)
The trivial matrix multiplication algorithm runs in $O(n^3)$, which proves $2 \leq \omega \leq 3$.
(2)
This trivial upper bound was improved upon many times [4].
Strassen [2] proved $\omega \leq \log_2(7) \leq 2.8074$.
Alman and Vassilevska--Williams [1] proved the most recent bound $\omega \leq 2.3728596$.
References
[1]
Josh Alman and Virginia Vassilevska Williams, "A Refined Laser Method and Faster Matrix Multiplication", 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021) (arXiv)
[2]
Volker Strassen, "Gaussian elimination is not optimal", Numerische Mathematik. 13 (4): 354-356, 1969. (doi)