Computational complexity of matrix multiplication
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 right amount of time it should take is of major practical relevance. Directly applying the mathematical definition of matrix multiplication gives an algorithm that requires field operations to multiply two matrices over that field ( 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". The optimal number of field operations needed to multiply two square matrices up to constant factors is still unknown. This is a major open question in theoretical computer science. , the matrix multiplication algorithm with best asymptotic complexity runs in time, given by Josh Alman and Virginia Vassilevska Williams. 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. Simple algorithms. If "A", "B" are matrices over a field, then their product "AB" is also an matrix over that field, defined entrywise as Schoolbook algorithm. The simplest approach to computing the product of two matrices "A" and "B" is to compute the arithmetic expressions coming from the definition of matrix multiplication. In pseudocode: This algorithm requires, in the worst case, multiplications of scalars and additions for computing the product of two square matrices. Its computational complexity is therefore , 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. Strassen's algorithm improves on naive matrix multiplication through a divide-and-conquer approach. The key observation is that multiplying two matrices can be done with only 7 multiplications, instead of the usual 8 (at the expense of several additional addition and subtraction operations). This means that, treating the input matrices as block matrices, the task of multiplying matrices can be reduced to 7 subproblems of multiplying matrices. Applying this recursively gives an algorithm  needing formula_2 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, but it is faster in cases where or so and appears in several libraries, such as BLAS. It is very useful for large matrices over exact domains such as finite fields, where numerical stability is not an issue. Matrix multiplication exponent. The "matrix multiplication exponent", usually denoted , is the smallest real number for which any formula_3 matrix over a field can be multiplied together using formula_4 field operations. This notation is commonly used  in algorithms research, so that algorithms using matrix multiplication as a subroutine have meaningful bounds on running time regardless of the true value of . Using a naive lower bound and schoolbook matrix multiplication for the upper bound, one can straightforwardly conclude that . Whether 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 . The current best bound on is , by Josh Alman and Virginia Vassilevska Williams. This algorithm, like all other recent algorithms in this line of research, uses 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. The conceptual idea of these algorithms are similar to Strassen's algorithm: a way is devised for multiplying two -matrices with fewer than multiplications, and this technique is applied recursively. The laser method has limitations to its power, and cannot be used to show that . 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. 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. Several of their conjectures have since been disproven by Blasiak, Cohn, Church, Grochow , Naslund, Sawin, and Umans using the Slice Rank method. 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. Lower bounds for ω. There is a trivial lower bound of . Since any algorithm for multiplying two -matrices has to process all entries, there is a trivial asymptotic lower bound of operations for any matrix multiplication algorithm. Thus . It is unknown whether . The best known lower bound for matrix-multiplication complexity is , for bounded coefficient arithmetic circuits over the real or complex numbers, and  is due to Ran Raz. Rectangular matrix multiplication. Similar techniques also apply to rectangular matrix multiplication. The central object of study is formula_5, which is the smallest formula_6 such that one can multiply a matrix of size formula_7 with a matrix of size formula_8 with formula_9 arithmetic operations. A result in algebraic complexity states that multiplying matrices of size formula_7 and formula_8 requires the same number of arithmetic operations as multiplying matrices of size formula_7 and formula_13 and of size formula_13 and formula_7, so this encompasses the complexity of rectangular matrix multiplication. This generalizes the square matrix multiplication exponent, since  formula_16. Of interest is proving that, for values of "k" between 0 and 1, that formula_17. Since the output of the matrix multiplication problem is size formula_18, formula_19 always, so these results show that formula_20 exactly. The largest "k" such that formula_20 is known as the "dual matrix multiplication exponent", usually denoted "α". "α" is referred to as the "dual" because showing that formula_22 is equivalent to showing that formula_23. Like the matrix multiplication exponent, the dual matrix multiplication exponent sometimes appears in the complexity of algorithms in numerical linear algebra and optimization. The first bound on "α" is by  Coppersmith in 1982, who showed that formula_24. The current best bound on "α" is formula_25, given by Le Gall and Urrutia. This paper also contains bounds on formula_5. Related complexities. 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 formula_27 include characteristic polynomial, eigenvalues (but not eigenvectors), Hermite normal form, and Smith normal form. Matrix inversion, determinant and Gaussian elimination. In his 1969 paper, where he proved the complexity formula_28 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 formula_29 for some formula_30 The starting point of Strassen's proof is using block matrix multiplication. Specifically, a matrix of even dimension may be partitioned in four blocks Under this form, its inverse is provided that and formula_33 are invertible. Thus, the inverse of a matrix may be computed with two inversions, six multiplications and four additions or additive inverses of matrices. It follows that, denoting respectively  by , and the number of operations needed for inverting, multiplying and adding matrices, one has If formula_35 one may apply this formula recursively: If formula_37 and formula_38 one gets eventually for some constant . 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 is invertible, the equality defines a block LU decomposition that may be applied recursively to formula_41 and formula_42 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