Computational complexity of matrix multiplication

Unsolved problem in computer science:

What is the fastest algorithm for matrix multiplication?

(more unsolved problems in computer science)

In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the fastest algorithm for matrix multiplication is of major practical relevance.

Directly applying the mathematical definition of matrix multiplication gives an algorithm that requires n³ field operations to multiply two n × n matrices over that field (Θ(n³) in big O notation). Surprisingly, algorithms exist that provide better running times than this straightforward "schoolbook algorithm". The first to be discovered was Strassen's algorithm, devised by Volker Strassen in 1969 and often referred to as "fast matrix multiplication". ^[1] The optimal number of field operations needed to multiply two square n × n matrices up to constant factors is still unknown. This is a major open question in theoretical computer science.

As of January 2024 ^[update] , the best bound on the asymptotic complexity of a matrix multiplication algorithm is O(n^2.371552). ^{[2] [3]} However, this and similar improvements to Strassen are not used in practice, because they are galactic algorithms: the constant coefficient hidden by the big O notation is so large that they are only worthwhile for matrices that are too large to handle on present-day computers. ^{[4] [5]}

Simple algorithms

If A, B are n × n matrices over a field, then their product AB is also an n × n matrix over that field, defined entrywise as

${\displaystyle (AB)_{ij}=\sum _{k=1}^{n}A_{ik}B_{kj}.}$

Schoolbook algorithm

For implementation techniques (in particular parallel and distributed algorithms), see Matrix multiplication algorithm.

The simplest approach to computing the product of two n × n matrices A and B is to compute the arithmetic expressions coming from the definition of matrix multiplication. In pseudocode:

inputA and B, both n by n matrices initializeC to be an n by n matrix of all zeros fori from 1 to n:     forj from 1 to n:         fork from 1 to n:             C[i][j] = C[i][j] + A[i][k]*B[k][j] outputC (as A*B)

This algorithm requires, in the worst case, ⁠${\displaystyle n^{3}}$⁠ multiplications of scalars and ⁠${\displaystyle n^{3}-n^{2}}$⁠ additions for computing the product of two square n×n matrices. Its computational complexity is therefore ⁠${\displaystyle O(n^{3})}$⁠, in a model of computation where field operations (addition and multiplication) take constant time (in practice, this is the case for floating point numbers, but not necessarily for integers).

Strassen's algorithm

Main article: Strassen algorithm

Strassen's algorithm improves on naive matrix multiplication through a divide-and-conquer approach. The key observation is that multiplying two 2 × 2 matrices can be done with only 7 multiplications, instead of the usual 8 (at the expense of 11 additional addition and subtraction operations). This means that, treating the input n×n matrices as block 2 × 2 matrices, the task of multiplying n×n matrices can be reduced to 7 subproblems of multiplying n/2×n/2 matrices. Applying this recursively gives an algorithm needing ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$ field operations.

Unlike algorithms with faster asymptotic complexity, Strassen's algorithm is used in practice. The numerical stability is reduced compared to the naive algorithm, ^[6] but it is faster in cases where n > 100 or so ^[7] and appears in several libraries, such as BLAS. ^[8] Fast matrix multiplication algorithms cannot achieve component-wise stability, but some can be shown to exhibit norm-wise stability. ^[9] It is very useful for large matrices over exact domains such as finite fields, where numerical stability is not an issue.

Matrix multiplication exponent

Improvement of estimates of exponent ω over time for the computational complexity of matrix multiplication ${\displaystyle O(n^{\omega })}$

Closeup of 1990–2024

Timeline of matrix multiplication exponent

Year	Bound on omega	Authors
1969	2.8074	Strassen [1]
1978	2.796	Pan [10]
1979	2.780	Bini, Capovani  [ it ], Romani [11]
1981	2.522	Schönhage [12]
1981	2.517	Romani [13]
1981	2.496	Coppersmith, Winograd [14]
1986	2.479	Strassen [15]
1990	2.3755	Coppersmith, Winograd [16]
2010	2.3737	Stothers [17]
2012	2.3729	Williams [18] [19]
2014	2.3728639	Le Gall [20]
2020	2.3728596	Alman, Williams [21] [22]
2022	2.371866	Duan, Wu, Zhou [23]
2024	2.371552	Williams, Xu, Xu, and Zhou [2]
2024	2.371339	Alman, Duan, Williams, Xu, Xu, and Zhou [24]

The matrix multiplication exponent, usually denoted ω, is the smallest real number for which any two ${\displaystyle n\times n}$ matrices over a field can be multiplied together using ${\displaystyle n^{\omega +o(1)}}$ field operations. This notation is commonly used in algorithms research, so that algorithms using matrix multiplication as a subroutine have bounds on running time that can update as bounds on ω improve.

Using a naive lower bound and schoolbook matrix multiplication for the upper bound, one can straightforwardly conclude that 2 ≤ ω ≤ 3. Whether ω = 2 is a major open question in theoretical computer science, and there is a line of research developing matrix multiplication algorithms to get improved bounds on ω.

All recent algorithms in this line of research use the laser method, a generalization of the Coppersmith–Winograd algorithm, which was given by Don Coppersmith and Shmuel Winograd in 1990 and was the best matrix multiplication algorithm until 2010. ^[25] The conceptual idea of these algorithms is similar to Strassen's algorithm: a way is devised for multiplying two k × k-matrices with fewer than k³ multiplications, and this technique is applied recursively. The laser method has limitations to its power, Ambainis, Filmus and Le Gall prove that it cannot be used to show that ω < 2.3725 by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd and neither ω < 2.3078 for a wide class of variants of this approach. ^[26] In 2022 Duan, Wu and Zhou devised a variant breaking the first of the two barriers with ω < 2.37188, ^[23] they do so by identifying a source of potential optimization in the laser method termed combination loss for which they compensate using an asymmetric version of the hashing method in the Coppersmith–Winograd algorithm.

Group theory reformulation of matrix multiplication algorithms

Henry Cohn, Robert Kleinberg, Balázs Szegedy and Chris Umans put methods such as the Strassen and Coppersmith–Winograd algorithms in an entirely different group-theoretic context, by utilising triples of subsets of finite groups which satisfy a disjointness property called the triple product property (TPP). They also give conjectures that, if true, would imply that there are matrix multiplication algorithms with essentially quadratic complexity. This implies that the optimal exponent of matrix multiplication is 2, which most researchers believe is indeed the case. ^[5] One such conjecture is that families of wreath products of Abelian groups with symmetric groups realise families of subset triples with a simultaneous version of the TPP. ^{[27] [28]} Several of their conjectures have since been disproven by Blasiak, Cohn, Church, Grochow, Naslund, Sawin, and Umans using the Slice Rank method. ^[29] Further, Alon, Shpilka and Chris Umans have recently shown that some of these conjectures implying fast matrix multiplication are incompatible with another plausible conjecture, the sunflower conjecture, ^[30] which in turn is related to the cap set problem. ^[29]

Lower bounds for ω

There is a trivial lower bound of ⁠${\displaystyle \omega \geq 2}$⁠. Since any algorithm for multiplying two n × n-matrices has to process all 2n² entries, there is a trivial asymptotic lower bound of Ω(n²) operations for any matrix multiplication algorithm. Thus ⁠${\displaystyle 2\leq \omega <2.37188}$⁠. It is unknown whether ⁠${\displaystyle \omega >2}$⁠. The best known lower bound for matrix-multiplication complexity is Ω(n² log(n)), for bounded coefficient arithmetic circuits over the real or complex numbers, and is due to Ran Raz. ^[31]

The exponent ω is defined to be a limit point, in that it is the infimum of the exponent over all matrix multiplication algorithms. It is known that this limit point is not achieved. In other words, under the model of computation typically studied, there is no matrix multiplication algorithm that uses precisely O(n^ω) operations; there must be an additional factor of n^o(1). ^[14]

Rectangular matrix multiplication

Similar techniques also apply to rectangular matrix multiplication. The central object of study is ${\displaystyle \omega (k)}$, which is the smallest ${\displaystyle c}$ such that one can multiply a matrix of size ${\displaystyle n\times \lceil n^{k}\rceil }$ with a matrix of size ${\displaystyle \lceil n^{k}\rceil \times n}$ with ${\displaystyle O(n^{c+o(1)})}$ arithmetic operations. A result in algebraic complexity states that multiplying matrices of size ${\displaystyle n\times \lceil n^{k}\rceil }$ and ${\displaystyle \lceil n^{k}\rceil \times n}$ requires the same number of arithmetic operations as multiplying matrices of size ${\displaystyle n\times \lceil n^{k}\rceil }$ and ${\displaystyle n\times n}$ and of size ${\displaystyle n\times n}$ and ${\displaystyle n\times \lceil n^{k}\rceil }$, so this encompasses the complexity of rectangular matrix multiplication. ^[32] This generalizes the square matrix multiplication exponent, since ${\displaystyle \omega (1)=\omega }$.

Since the output of the matrix multiplication problem is size ${\displaystyle n^{2}}$, we have ${\displaystyle \omega (k)\geq 2}$ for all values of ${\displaystyle k}$. If one can prove for some values of ${\displaystyle k}$ between 0 and 1 that ${\displaystyle \omega (k)\leq 2}$, then such a result shows that ${\displaystyle \omega (k)=2}$ for those ${\displaystyle k}$. The largest k such that ${\displaystyle \omega (k)=2}$ is known as the dual matrix multiplication exponent, usually denoted α. α is referred to as the "dual" because showing that ${\displaystyle \alpha =1}$ is equivalent to showing that ${\displaystyle \omega =2}$. Like the matrix multiplication exponent, the dual matrix multiplication exponent sometimes appears in the complexity of algorithms in numerical linear algebra and optimization. ^[33]

The first bound on α is by Coppersmith in 1982, who showed that ${\displaystyle \alpha >0.17227}$. ^[34] The current best peer-reviewed bound on α is ${\displaystyle \alpha \geq 0.321334}$, given by Williams, Xu, Xu, and Zhou. ^[2]

Related problems

Further information: Computational complexity of mathematical operations § Matrix algebra

Problems that have the same asymptotic complexity as matrix multiplication include determinant, matrix inversion, Gaussian elimination (see next section). Problems with complexity that is expressible in terms of ${\displaystyle \omega }$ include characteristic polynomial, eigenvalues (but not eigenvectors), Hermite normal form, and Smith normal form.^{[ citation needed ]}

Matrix inversion, determinant and Gaussian elimination

In his 1969 paper, where he proved the complexity ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$ for matrix computation, Strassen proved also that matrix inversion, determinant and Gaussian elimination have, up to a multiplicative constant, the same computational complexity as matrix multiplication. The proof does not make any assumptions on matrix multiplication that is used, except that its complexity is ${\displaystyle O(n^{\omega })}$ for some ${\displaystyle \omega \geq 2}$

The starting point of Strassen's proof is using block matrix multiplication. Specifically, a matrix of even dimension 2n×2n may be partitioned in four n×n blocks

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}.}$

Under this form, its inverse is

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}^{-1}={\begin{bmatrix}{A}^{-1}+{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&-{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}\\-({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&({D}-{CA}^{-1}{B})^{-1}\end{bmatrix}},}$

provided that A and ${\displaystyle {D}-{CA}^{-1}{B}}$ are invertible.

Thus, the inverse of a 2n×2n matrix may be computed with two inversions, six multiplications and four additions or additive inverses of n×n matrices. It follows that, denoting respectively by I(n), M(n) and A(n) = n² the number of operations needed for inverting, multiplying and adding n×n matrices, one has

${\displaystyle I(2n)\leq 2I(n)+6M(n)+4A(n).}$

If ${\displaystyle n=2^{k},}$ one may apply this formula recursively:

${\displaystyle {\begin{aligned}I(2^{k})&\leq 2I(2^{k-1})+6M(2^{k-1})+4A(2^{k-1})\\&\leq 2^{2}I(2^{k-2})+6(M(2^{k-1})+2M(2^{k-2}))+4(A(2^{k-1})+2A(2^{k-2}))\\&\,\,\,\vdots \end{aligned}}}$

If ${\displaystyle M(n)\leq cn^{\omega },}$ and ${\displaystyle \alpha =2^{\omega }\geq 4,}$ one gets eventually

${\displaystyle {\begin{aligned}I(2^{k})&\leq 2^{k}I(1)+6c(\alpha ^{k-1}+2\alpha ^{k-2}+\cdots +2^{k-1}\alpha ^{0})+k2^{k+1}\\&\leq 2^{k}+6c{\frac {\alpha ^{k}-2^{k}}{\alpha -2}}+k2^{k+1}\\&\leq d(2^{k})^{\omega }\end{aligned}}}$

for some constant d.

For matrices whose dimension is not a power of two, the same complexity is reached by increasing the dimension of the matrix to a power of two, by padding the matrix with rows and columns whose entries are 1 on the diagonal and 0 elsewhere.

This proves the asserted complexity for matrices such that all submatrices that have to be inverted are indeed invertible. This complexity is thus proved for almost all matrices, as a matrix with randomly chosen entries is invertible with probability one.

The same argument applies to LU decomposition, as, if the matrix A is invertible, the equality

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}={\begin{bmatrix}I&0\\CA^{-1}&I\end{bmatrix}}\,{\begin{bmatrix}A&B\\0&D-CA^{-1}B\end{bmatrix}}}$

defines a block LU decomposition that may be applied recursively to ${\displaystyle A}$ and ${\displaystyle D-CA^{-1}B,}$ for getting eventually a true LU decomposition of the original matrix.

The argument applies also for the determinant, since it results from the block LU decomposition that

${\displaystyle \det {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}=\det(A)\det(D-CA^{-1}B).}$

Minimizing number of multiplications

Related to the problem of minimizing the number of arithmetic operations is minimizing the number of multiplications, which is typically a more costly operation than addition. A ${\displaystyle O(n^{\omega })}$ algorithm for matrix multiplication must necessarily only use ${\displaystyle O(n^{\omega })}$ multiplication operations, but these algorithms are impractical. Improving from the naive ${\displaystyle n^{3}}$ multiplications for schoolbook multiplication, ${\displaystyle 4\times 4}$ matrices in ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$ can be done with 47 multiplications, ^[35] ${\displaystyle 3\times 3}$ matrix multiplication over a commutative ring can be done in 21 multiplications ^{[36] [37]} (23 if non-commutative ^[38] ). The lower bound of multiplications needed is 2mn+2n−m−2 (multiplication of n×m-matrices with m×n-matrices using the substitution method, m⩾n⩾3), which means n=3 case requires at least 19 multiplications and n=4 at least 34. ^[39] For n=2 optimal 7 multiplications 15 additions are minimal, compared to only 4 additions for 8 multiplications. ^{[40] [41]}

See also

• Computational complexity of mathematical operations
• CYK algorithm, §Valiant's algorithm
• Freivalds' algorithm, a simple Monte Carlo algorithm that, given matrices A, B and C, verifies in Θ(n²) time if AB = C.
• Matrix chain multiplication
• Matrix multiplication, for abstract definitions
• Matrix multiplication algorithm, for practical implementation details
• Sparse matrix–vector multiplication

References

1. Volker Strassen (Aug 1969). "Gaussian elimination is not optimal". Numerische Mathematik. 13 (4): 354–356. doi:10.1007/BF02165411. S2CID   121656251.
2. Vassilevska Williams, Virginia; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei. New Bounds for Matrix Multiplication: from Alpha to Omega. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pp. 3792–3835. arXiv: 2307.07970 . doi:10.1137/1.9781611977912.134.
3. Nadis, Steve (March 7, 2024). "New Breakthrough Brings Matrix Multiplication Closer to Ideal" . Retrieved 2024-03-09.
4. Iliopoulos, Costas S. (1989). "Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix" (PDF). SIAM Journal on Computing. 18 (4): 658–669. CiteSeerX   10.1.1.531.9309 . doi:10.1137/0218045. MR   1004789. Archived from the original (PDF) on 2014-03-05. Retrieved 2015-01-16. The Coppersmith–Winograd algorithm is not practical, due to the very large hidden constant in the upper bound on the number of multiplications required.
5. Robinson, Sara (November 2005). "Toward an Optimal Algorithm for Matrix Multiplication" (PDF). SIAM News. 38 (9). Even if someone manages to prove one of the conjectures—thereby demonstrating that ω = 2—the wreath product approach is unlikely to be applicable to the large matrix problems that arise in practice. [...] the input matrices must be astronomically large for the difference in time to be apparent.
6. Miller, Webb (1975). "Computational complexity and numerical stability". SIAM News. 4 (2): 97–107. CiteSeerX   10.1.1.148.9947 . doi:10.1137/0204009.
7. Skiena, Steven (2012). "Sorting and Searching". The Algorithm Design Manual . Springer. pp.  45–46, 401–403. doi:10.1007/978-1-84800-070-4_4. ISBN   978-1-84800-069-8.
8. Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press. p.  108. ISBN   978-0-521-88068-8.
9. Ballard, Grey; Benson, Austin R.; Druinsky, Alex; Lipshitz, Benjamin; Schwartz, Oded (2016). "Improving the numerical stability of fast matrix multiplication". SIAM Journal on Matrix Analysis and Applications. 37 (4): 1382–1418. arXiv: 1507.00687 . doi:10.1137/15M1032168. S2CID   2853388.
10. Victor Yakovlevich Pan (Oct 1978). "Strassen's Algorithm is not Optimal: Trilinear Technique of Aggregating, Uniting and Canceling for Constructing Fast Algorithms for Matrix Operations". Proc. 19th FOCS. pp. 166–176. doi:10.1109/SFCS.1978.34. S2CID   14348408.
11. Dario Andrea Bini; Milvio Capovani; Francesco Romani; Grazia Lotti (Jun 1979). "${\displaystyle O(n^{2.7799})}$ complexity for ${\displaystyle n\times n}$ approximate matrix multiplication". Information Processing Letters. 8 (5): 234–235. doi:10.1016/0020-0190(79)90113-3.
12. A. Schönhage (1981). "Partial and total matrix multiplication". SIAM Journal on Computing. 10 (3): 434–455. doi:10.1137/0210032.
13. Francesco Romani (1982). "Some properties of disjoint sums of tensors related to matrix multiplication". SIAM Journal on Computing. 11 (2): 263–267. doi:10.1137/0211020.
14. D. Coppersmith; S. Winograd (1981). "On the asymptotic complexity of matrix multiplication". Proc. 22nd Annual Symposium on Foundations of Computer Science (FOCS). pp. 82–90. doi:10.1109/SFCS.1981.27. S2CID   206558664.
15. Volker Strassen (Oct 1986). "The asymptotic spectrum of tensors and the exponent of matrix multiplication". Proc. 27th Ann. Symp. on Foundation of Computer Science (FOCS). pp. 49–54. doi:10.1109/SFCS.1986.52. ISBN   0-8186-0740-8. S2CID   15077423.
16. D. Coppersmith; S. Winograd (Mar 1990). "Matrix multiplication via arithmetic progressions". Journal of Symbolic Computation. 9 (3): 251–280. doi: 10.1016/S0747-7171(08)80013-2 .
17. Stothers, Andrew James (2010). On the complexity of matrix multiplication (Ph.D. thesis). University of Edinburgh.
18. Virginia Vassilevska Williams (2012). "Multiplying Matrices Faster than Coppersmith-Winograd". In Howard J. Karloff; Toniann Pitassi (eds.). Proc. 44th Symposium on Theory of Computing (STOC). ACM. pp. 887–898. doi:10.1145/2213977.2214056. ISBN   978-1-4503-1245-5. S2CID   14350287.
19. Williams, Virginia Vassilevska. Multiplying matrices in ${\displaystyle O(n^{2.373})}$ time (PDF) (Technical Report). Stanford University.
20. Le Gall, François (2014). "Algebraic complexity theory and matrix multiplication". In Katsusuke Nabeshima (ed.). Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation - ISSAC '14. pp. 296–303. arXiv: 1401.7714 . Bibcode:2014arXiv1401.7714L. doi:10.1145/2608628.2627493. ISBN   978-1-4503-2501-1. S2CID   2597483.
21. Alman, Josh; Williams, Virginia Vassilevska (2020). "A Refined Laser Method and Faster Matrix Multiplication". 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021). arXiv: 2010.05846 .
22. Hartnett, Kevin (23 March 2021). "Matrix Multiplication Inches Closer to Mythic Goal". Quanta Magazine. Retrieved 2021-04-01.
23. Duan, Ran; Wu, Hongxun; Zhou, Renfei (2022). "Faster Matrix Multiplication via Asymmetric Hashing". arXiv: 2210.10173 [cs.DS].
24. Alman, Josh; Duan, Ran; Williams, Virginia Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfai (2024). "More Asymmetry Yields Faster Matrix Multiplication". arXiv: 2404.16349 [cs.DS].
25. Coppersmith, Don; Winograd, Shmuel (1990). "Matrix multiplication via arithmetic progressions" (PDF). Journal of Symbolic Computation. 9 (3): 251. doi: 10.1016/S0747-7171(08)80013-2 .
26. Ambainis, Andris; Filmus, Yuval; Le Gall, François (2015-06-14). "Fast Matrix Multiplication". Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. STOC '15. Portland, Oregon, USA: Association for Computing Machinery. pp. 585–593. arXiv: 1411.5414 . doi:10.1145/2746539.2746554. ISBN   978-1-4503-3536-2. S2CID   8332797.
27. Cohn, H.; Kleinberg, R.; Szegedy, B.; Umans, C. (2005). "Group-theoretic Algorithms for Matrix Multiplication". 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). p. 379. doi:10.1109/SFCS.2005.39. ISBN   0-7695-2468-0. S2CID   41278294.
28. Cohn, Henry; Umans, Chris (2003). "A Group-theoretic Approach to Fast Matrix Multiplication". Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 11–14 October 2003. IEEE Computer Society. pp. 438–449. arXiv: math.GR/0307321 . doi:10.1109/SFCS.2003.1238217. ISBN   0-7695-2040-5. S2CID   5890100.
29. Blasiak, J.; Cohn, H.; Church, T.; Grochow, J.; Naslund, E.; Sawin, W.; Umans, C. (2017). "On cap sets and the group-theoretic approach to matrix multiplication". Discrete Analysis. p. 1245. doi:10.19086/da.1245. S2CID   9687868.
30. Alon, N.; Shpilka, A.; Umans, C. (April 2011). "On Sunflowers and Matrix Multiplication". Electronic Colloquium on Computational Complexity. TR11-067.
31. Raz, Ran (2002). "On the complexity of matrix product". Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. pp. 144–151. doi:10.1145/509907.509932. ISBN   1581134959. S2CID   9582328.
32. Gall, Francois Le; Urrutia, Florent (2018-01-01). Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. Proceedings. Society for Industrial and Applied Mathematics. pp. 1029–1046. arXiv: 1708.05622 . doi:10.1137/1.9781611975031.67. ISBN   978-1-61197-503-1. S2CID   33396059 . Retrieved 2021-05-23.{{cite book}}: |work= ignored (help)
33. Cohen, Michael B.; Lee, Yin Tat; Song, Zhao (2021-01-05). "Solving Linear Programs in the Current Matrix Multiplication Time". Journal of the ACM. 68 (1): 3:1–3:39. arXiv: 1810.07896 . doi:10.1145/3424305. ISSN   0004-5411. S2CID   231955576.
34. Coppersmith, D. (1982-08-01). "Rapid Multiplication of Rectangular Matrices" . SIAM Journal on Computing. 11 (3): 467–471. doi:10.1137/0211037. ISSN   0097-5397.
35. See Extended Data Fig. 1: Algorithm for multiplying 4 × 4 matrices in modular arithmetic (${\displaystyle \mathbb {Z} _{2}}$)) with 47 multiplications in Fawzi, A.; Balog, M.; Huang, A.; Hubert, T.; Romera-Paredes, B.; Barekatain, M.; Novikov, A.; r Ruiz, F. J.; Schrittwieser, J.; Swirszcz, G.; Silver, D.; Hassabis, D.; Kohli, P. (2022). "Discovering faster matrix multiplication algorithms with reinforcement learning". Nature. 610 (7930): 47–53. Bibcode:2022Natur.610...47F. doi:10.1038/s41586-022-05172-4. PMC   9534758 . PMID   36198780.
36. Rosowski, Andreas (2020-07-27). "Fast Commutative Matrix Algorithm". arXiv: 1904.07683 .{{cite journal}}: Cite journal requires |journal= (help)
37. Makarov, O. M. (1986). "An algorithm for multiplying 3×3 matrices". Zhurnal Vychislitel'noi Matematiki I Matematicheskoi Fiziki. 26 (2): 293–294. Retrieved 5 October 2022.

    Also in Makarov, O. M. (1986). "An algorithm for multiplying 3×3 matrices". USSR Computational Mathematics and Mathematical Physics. 26: 179–180. doi:10.1016/0041-5553(86)90203-X.

38. Laderman, Julian D. (1976). "A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications". Bulletin of the American Mathematical Society. 82 (1): 126–128. doi: 10.1090/S0002-9904-1976-13988-2 . ISSN   0002-9904.
39. Bläser, Markus (February 2003). "On the complexity of the multiplication of matrices of small formats". Journal of Complexity. 19 (1): 43–60. doi: 10.1016/S0885-064X(02)00007-9 .
40. Winograd, S. (1971-10-01). "On multiplication of 2 × 2 matrices". Linear Algebra and Its Applications. 4 (4): 381–388. doi: 10.1016/0024-3795(71)90009-7 . ISSN   0024-3795.
41. L., Probert, R. (1973). On the complexity of matrix multiplication. University of Waterloo. OCLC   1124200063.

External links

• Yet another catalogue of fast matrix multiplication algorithms
• Fawzi, A.; Balog, M.; Huang, A.; Hubert, T.; Romera-Paredes, B.; Barekatain, M.; Novikov, A.; Ruiz, F.J.R.; Schrittwieser, J.; Swirszcz, G.; Silver, D.; Hassabis, D.; Kohli, P. (2022). "Discovering faster matrix multiplication algorithms with reinforcement learning". Nature. 610 (7930): 47–53. Bibcode:2022Natur.610...47F. doi:10.1038/s41586-022-05172-4. PMC   9534758 . PMID   36198780.