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". 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.371339). 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.

If A, B are two 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}.}$$

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:

This algorithm requires ⁠${\displaystyle n^{3}}$⁠ multiplications and ⁠${\displaystyle n^{3}-n^{2}}$⁠ additions of scalars 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 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 seven multiplications, instead of the usual eight (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 two n×n matrices can be reduced to seven subproblems of multiplying two 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, but it is faster in cases where n > 100 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.