Exponent of matrix multiplication complexity

edit · history · discussion · short url · complexity matrix multiplication algorithms

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$.

Comments

(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)

Links

[3]

Wikipedia: Matrix multiplication algorithm

[4]

Wikipedia: Matrix multiplication/computational complexity

Data properties

Entries are of type: real number

Sources of data: [1]

How well the digits are known: proven

How they were obtained:

Not a computed value: the entry is an interval between two theorems, the trivial lower bound of 2 and the best upper bound published when the entry was written. The true exponent is not known, and the width of the interval is ignorance about mathematics rather than error in a computation. Sharper upper bounds have been published since.