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 best announced bound on the asymptotic complexity of a matrix multiplication algorithm is time, given by Williams, Xu, Xu, and Zhou, announced in a preprint. This improves on the bound of given by a preprint of Duan, Wu and Zhou. 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. The best time-bound confirmed by peer review is .
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:
input A and B, both n by n matrices
initialize C to be an n by n matrix of all zeros
for i from 1 to n: for j from 1 to n: for k from 1 to n: C[i][j] = C[i][j] + A[i][k]*B[k][j] output C (as A*B)
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 11 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 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. Fast matrix multiplication algorithms cannot achieve component-wise stability, but some can be shown to exhibit norm-wise stability. 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 two matrices over a field can be multiplied together using 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 . 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 .