Intheoretical computer science, thecomputational complexity of matrix multiplication dictateshow quickly the operation ofmatrix multiplication can be performed.Matrix multiplication algorithms are a central subroutine in theoretical andnumerical algorithms fornumerical linear algebra andoptimization, 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 requiresn³field operations to multiply twon ×n matrices over that field (Θ(n³) inbig O notation). Surprisingly, algorithms exist that provide better running times than this straightforward "schoolbook algorithm". The first to be discovered wasStrassen's algorithm, devised byVolker Strassen in 1969 and often referred to as "fast matrix multiplication".^[1] The optimal number of field operations needed to multiply two squaren ×n matricesup to constant factors is still unknown. This is a major open question intheoretical computer science.

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

IfA,B are twon ×n matrices over a field, then their productAB is also ann ×n matrix over that field, defined entrywise as$${\displaystyle (AB{)}_{ij}=\sum _{k=1}^n{A}_{ik}{B}_{kj}.}$$

The simplest approach to computing the product of twon ×n matricesA andB is to compute the arithmetic expressions coming from the definition of matrix multiplication. Inpseudocode:

inputA andB, bothn byn matricesinitializeC to be ann byn matrix of all zerosfori from 1 ton:forj from 1 ton:fork from 1 ton:C[i][j] =C[i][j] +A[i][k]*B[k][j]outputC (as A*B)

Thisalgorithm requires⁠${\displaystyle n^3}$⁠ multiplications and⁠${\displaystyle n^3-n^2}$⁠ additions of scalars for computing the product of two squaren×n matrices. Itscomputational complexity is therefore⁠${\displaystyle O(n^3)}$⁠, in amodel of computation where field operations (addition and multiplication) take constant time (in practice, this is the case forfloating point numbers, but not necessarily for integers).

Strassen's algorithm improves on naive matrix multiplication through adivide-and-conquer approach. The key observation is that multiplying two2 × 2 matrices can be done with only seven multiplications, instead of the usual eight (at the expense of 11 additional addition and subtraction operations). This means that, treating the inputn×n matrices asblock2 × 2 matrices, the task of multiplying twon×n matrices can be reduced to seven subproblems of multiplying twon/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. Thenumerical stability is reduced compared to the naive algorithm,^[5] but it is faster in cases wheren > 100 or so^[6] and appears in several libraries, such asBLAS.^[7] Fast matrix multiplication algorithms cannot achievecomponent-wise stability, but some can be shown to exhibitnorm-wise stability.^[8] It is very useful for large matrices over exact domains such asfinite fields, where numerical stability is not an issue.

Thematrix multiplication exponent, usually denotedω, is the smallestreal 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 inalgorithms 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 that2 ≤ω ≤ 3. Whetherω = 2 is a major open question intheoretical 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 thelaser method, a generalization of the Coppersmith–Winograd algorithm, which was given byDon Coppersmith andShmuel Winograd in 1990 and was the best matrix multiplication algorithm until 2010.^[24] The conceptual idea of these algorithms is similar to Strassen's algorithm: a method is devised for multiplying twok ×k-matrices with fewer thank³ multiplications, and this technique is applied recursively. The laser method has limitations to its power:Ambainis, Filmus andLe 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.^[25] In 2022 Duan, Wu and Zhou devised a variant breaking the first of the two barriers withω < 2.37188,^[22] they do so by identifying a source of potential optimization in the laser method termedcombination loss for which they compensate using an asymmetric version of the hashing method in the Coppersmith–Winograd algorithm.

Nonetheless, the above are classical examples ofgalactic algorithms. On the opposite, the above Strassen's algorithm of 1969 andPan's algorithm of 1978, whose respective exponents are slightly above and below 2.78, have constant coefficients that make them feasible.^[26]

Henry Cohn,Robert Kleinberg,Balázs Szegedy andChris Umans put methods such as the Strassen and Coppersmith–Winograd algorithms in an entirely differentgroup-theoretic context, by utilising triples of subsets of finite groups which satisfy a disjointness property called thetriple 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.^[4] One such conjecture is that families ofwreath products ofAbelian 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 andChris Umans have recently shown that some of these conjectures implying fast matrix multiplication are incompatible with another plausible conjecture, thesunflower conjecture,^[30] which in turn is related to thecap set problem.^[29]

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

It is known that, under the model of computation typically studied, there is no matrix multiplication algorithm that uses preciselyO(n^ω) operations; there must be an additional factor ofn^o(1).^[13]

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)\ge 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)\le 2}$, then such a result shows that${\displaystyle \omega (k)=2}$ for those${\displaystyle k}$. The largestk such that${\displaystyle \omega (k)=2}$ is known as thedual 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 byCoppersmith in 1982, who showed that${\displaystyle \alpha >0.17227}$.^[34] The current best peer-reviewed bound onα is${\displaystyle \alpha \ge 0.321334}$, given by Williams, Xu, Xu, and Zhou.^[23]

Problems that have the same asymptotic complexity as matrix multiplication includedeterminant,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, andSmith normal form.^{[citation needed]}

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 thatmatrix inversion,determinant andGaussian elimination have, up to a multiplicative constant, the samecomputational 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 \ge 2}$.

The starting point of Strassen's proof is usingblock matrix multiplication. Specifically, a matrix of even dimension2n×2n may be partitioned in fourn×n blocksUnder this form, its inverse isprovided thatA and${\displaystyle D-{CA}^{-1}B}$ are invertible.

Thus, the inverse of a2n×2n matrix may be computed with two inversions, six multiplications and four additions or additive inverses ofn×n matrices. It follows that, denoting respectively byI(n),M(n) andA(n) =n² the number of operations needed for inverting, multiplying and addingn×n matrices, one has$${\displaystyle I(2n)\le 2I(n)+6M(n)+4A(n).}$$If${\displaystyle n=2^k,}$ one may apply this formula recursively:If${\displaystyle M(n)\le c{n}^{\omega },}$ and${\displaystyle \alpha =2^{\omega }\ge 4,}$ one gets eventuallyfor some constantd.

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 toLU decomposition, as, if the matrixA is invertible, the equality defines a block LU decomposition that may be applied recursively to${\displaystyle A}$ and${\displaystyle D-C{A}^{-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

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 acommutative 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 ofn×m matrices withm×n matrices using the substitution method,${\displaystyle m\ge n\ge 3}$), which means n=3 case requires at least 19 multiplications and n=4 at least 34.^[39] For n=2 optimal seven multiplications and 15 additions are minimal, compared to only four additions for eight multiplications.^[40][41]

• Computational complexity of mathematical operations
• CYK algorithm § Valiant's algorithm
• Freivalds' algorithm, a simpleMonte Carlo algorithm that, given matricesA,B andC, verifies inΘ(n²) time ifAB =C.
• Matrix chain multiplication
• Matrix multiplication, for abstract definitions
• Matrix multiplication algorithm, for practical implementation details
• Sparse matrix–vector multiplication

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

• Computer arithmetic algorithms
• Computational complexity theory
• Matrix theory
• Unsolved problems in computer science

• CS1: long volume value
• CS1 maint: multiple names: authors list
• Articles with short description
• Short description matches Wikidata
• Articles containing potentially dated statements from January 2024
• All articles containing potentially dated statements
• All articles with unsourced statements
• Articles with unsourced statements from March 2018