Difference between revisions
matrix-multiplication-omega
Status and infobox
- status:
—→ open - kind:
—→ problem - year:
—→ 1969 - statement:
—→ Is $\omega = 2$, that is, can two $n \times n$ matrices be multiplied in $n^{2+\varepsilon}$ operations for every $\varepsilon > 0$?
Source +18 −0
+---
+title: The exponent of matrix multiplication
+kind: problem
+status: open
+year: 1969
+authors: after Volker Strassen's $O(n^{2.81})$ algorithm
+statement: Is $\omega = 2$, that is, can two $n \times n$ matrices be multiplied in $n^{2+\varepsilon}$ operations for every $\varepsilon > 0$?
+space: algorithms
+---
+Strassen broke the $n^3$ barrier, and the bound has crept down since, to about 2.371 by 2024. Each step now wins in the third decimal place. AlphaTensor in 2022 found new small-case algorithms by search, showing that machine search can contribute. A faster algorithm is a checkable object; a lower bound would need a proof.
+
+Posed 1969, after Volker Strassen's $O(n^{2.81})$ algorithm.
+
+## Sources
+
+- [Wikipedia: Matrix multiplication algorithm](https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm)
+
+[[Space:algorithms|Algorithms]] · [[Continent:computation|Computation]]
Revision 65 as rendered
Strassen broke the barrier, and the bound has crept down since, to about 2.371 by 2024. Each step now wins in the third decimal place. AlphaTensor in 2022 found new small-case algorithms by search, showing that machine search can contribute. A faster algorithm is a checkable object; a lower bound would need a proof.
Posed 1969, after Volker Strassen's algorithm.