Matrix multiplication exponent
Description of constant
We define $C_{15}$ to be the matrix multiplication exponent $\omega$, the smallest real number such that two $n \times n$ matrices over a field can be multiplied using $O(n^{\omega + o(1)})$ arithmetic operations.
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| 3 | Trivial | |
| $\log_2 7 \approx 2.8074$ | [S1969] | Recursively uses an algorithm for $2 \times 2$ matrices with $7$ multiplication operations. |
| $\log_{70} 143640 \approx 2.7952$ | [P1978] | |
| $3 \log_{12} 10 \approx 2.7799$ | [BCRL1979, B1980] | Introduces approximate algorithms (border rank of tensors). |
| $3 \log_{436} 196 \approx 2.6054$ | [P1979] | |
| $\log_{48} 47216 \approx 2.7802$ | [P1980] | |
| $\log_{110} 140600 \approx 2.5218006$ | [S1981] | This and subsequent improvements use direct sum of several matrix multiplications, exploiting the fact that approximate complexity is not additive under such direct sums |
| $2.5161$ | [P1981] | |
| $2.5166$ | [R1982] | |
| $2.495548$ | [CW1982] | |
| $2.4785$ | [S1987] | Introduces laser method. |
| $2.375477$ | [CW1990] | Introduces Coppersmith-Winograd tensors. |
| $2.41$ | [CKSU2005] | Uses an alternative group-theoretic method. |
| $2.373689703$ | [S2010, DS2013] | This and subsequent improvements up to [L2014] modify and optimize the framework of Coppersmith-Winograd to analyze higher powers of the tensor. |
| $2.372873$ | [V2012, V2014] | |
| $2.373$ | [Z2012] | |
| $2.3728639$ | [L2014] | |
| $2.3728596$ | [AV2020] | Improved analysis of the laser method. |
| $2.371866$ | [DWZ23] | This and subsequent improvements introduce and optimize an asymmetric modification of the laser method. |
| $2.371552$ | [WXXZ24] | |
| $2.371339$ | [ADWXXZ25] |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $2$ | Trivial | Conjectured to be sharp. |
Additional comments and links
- The true value of $\omega$ affects the best possible running time of many other algorithms, including all-pairs shortest paths (APSP), transitive closure, and determinant computation.
- The constant can also be defined in terms of ranks of certain multilinear maps or tensors. Let $U, V, W$ be vector spaces over a field $k$. For a tensor $T \in U \otimes V \otimes W$ define its rank $R(T)$ as the minimal number of summands in the decompsition of $T$ into a sum of elementary tensors. Let $MM_n = \sum_{i,j,k = 1}^n e_{i,j} \otimes e_{j,k} \otimes e_{k, i} \in k^{n \times n} \otimes k^{n \times n} \otimes k^{n \times n}$ be the structure tensor of $n \times n$ matrix multiplication viewed as a bilinear map. Then $\omega = \inf \{ w \mid R(MM_n) = O(n^w) \}$ (see e.g. [B2013]).
- Strictly speaking, the value of $\omega$ may depend on the field over which we consider matrix multiplication. It is known that $\omega$ only depends on the characteristic of the field [S1981]. All known bounds are valid in every characteristic.
- Several surveys, lecture notes, and textbook treatments of the topic at different points of its development are available: [P1984], [G1987], [BCS1997](Chapter 15), [V2012a], [B2013], [LG2017], [L2017](Chapter 3).
- See also: Wikipedia page on matrix multiplication exponent.
References
- [S1969] Strassen, V. Gaussian elimination is not optimal. Numerische Mathematik 13 (1969), 354–356.
- [P1978] Pan, V. Ya. Strassen’s algorithm is not optimal: Trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations. In FOCS 1978, 166–176.
- [P1979] Pan, V. Ya. Field extension and trilinear aggregating, uniting and canceling for the acceleration of matrix multiplication. In FOCS 1979, 28–38.
- [BCRL79] Bini, D.; Capovani, M.; Romani, F.; Lotti, G. $O(n^{2.7799})$ complexity for $n \times n$ approximate matrix multiplication. Information Processing Lett. 8 (1979), 234–235.
- [B1980] Bini, D. Relations between exact and approximate bilinear algorithms. Applications. Calcolo 17 (1980), 87–97.
- [P1980] Pan, V. Ya. New fast algorithms for matrix operations. SIAM J. Computing 9 (1980), 321–342.
- [S1981] Schönhage, A. Partial and total matrix multiplication. SIAM J. Computing 10 (1981), 434–455.
- [P1981] Pan, V. Ya. New combinations of methods for the acceleration of matrix multiplication. Computers & Mathematics with Applications 7 (1981), 73–125.
- [R1982] Romani, F. Some properties of disjoint sums of tensors related to matrix multiplication. SIAM J. Computing 11 (1982), 263–267.
- [CW1982] Coppersmith, D.; Winograd, S. On the asymptotic complexity of matrix multiplication. SIAM J. Computing 11 (1982), 472–492.
- [P1984] Pan, V. Ya. How to multiply matrices faster. Lecture Notes Comp. Sci. 179, Springer (1984).
- [S1987] Strassen, V. Relative bilinear complexity and matrix multiplication. J. reine angew. Math. 375/376 (1987), 406–443.
- [G1987] de Groote, H. F. Lectures on the complexity of bilinear problems. Lecture Notes Comp. Sci. 245, Springer (1987).
- [CW1990] Coppersmith, D.; Winograd, S. Matrix multiplication via arithmetic progressions. J. Symbolic Computation 9 (1990), 251–280.
- [BCS1997] Bürgisser, P.; Clausen, M.; Shokrollahi, M. A. Algebraic complexity theory. Grundlehren der math. Wiss. 315, Springer (1997).
- [CKSU2005] Cohn, H.; Kleinberg, R.; Szegedy, B.; Umans, C. Group-theoretic algorithms for matrix multiplication. In FOCS 2005, 379–388.
- [S2010] Stothers, A. J. On the complexity of matrix multiplication. PhD thesis, University of Edinburgh (2010).
- [V2012] Vassilevska Williams, V. Multiplying matrices faster than Coppersmith–Winograd. In STOC 2012, 887–898.
- [V2012a] Vassilevska Williams, V. An overview of the recent progress on the exponent of matrix multiplication. SIGACT News 43(4) (2012), 57–59.
- [Z2012] Zhdanovich, D. V. The matrix capacity of a tensor. J. Mathematical Sciences 186 (2012), 599–643.
- [DS2013] Davie, A. M.; Stothers, A. J. Improved bound for complexity of matrix multiplication. Proc. Royal Society of Edinburgh A 143 (2013), 351–369.
- [B2013] Bläser, M. Fast matrix multiplication. Theory of Computing Graduate Surveys 5 (2013), 1–60.
- [V2014] Vassilevska Williams, V. Multiplying matrices in $O(n^{2.373})$ time. Unpublished note (2014), https://theory.stanford.edu/~virgi/matrixmult-f.pdf
- [LG2014] Le Gall, F. Powers of tensors and fast matrix multiplication. In ISSAC 2014, 296–303.
- [LG2017] Le Gall, F. Complexity of matrix multiplication and bilinear problems. Lecture notes for ADFOCS 2017 summer school. https://conferences.mpi-inf.mpg.de/adfocs-17/material/FLG_H1.pdf
- [L2017] Landsberg, J. M. Geometry and complexity theory. Cambridge Studies in Adv. Math. 169, Cambridge University Press (2017).
- [AV2020] Alman, J.; Vassilevska Williams, V. A refined laser method and faster matrix multiplication. TheoretiCS 3 (2024), article 21. Conference paper in SODA 2021, 522–539. arXiv:2010.05846.
- [DWZ2022] Duan, R; Wu, H.; Zhou, R. Faster matrix multiplication via asymmetric hashing. In FOCS 2023, 2129–2138. arXiv:2210.10173.
- [VXXZ2023] Vassilevska Williams, V.; Xu, Y.; Xu, Z.; Zhou, R. New bounds for matrix multiplication: from Alpha to Omega. In SODA 2024, 3792–3835. arXiv:2307.07970.
- [ADVXXZ2024] Alman, J.; Duan, R.; Vassilevska Williams, V.; Xu, Y.; Xu, Z.; Zhou, R. More asymmetry yields faster matrix multiplication. In SODA 2025, 2005–2039. arXiv:2404.16349.
Contribution notes
ChatGPT DeepResearch was used to prepare an initial version of this page.