In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used for matrix multiplication. It is asymptotically faster than the standard matrix multiplication algorithm, but slower than the fastest known algorithm, and is useful in practice for large matrices.
Contents 
Volker Strassen published the Strassen algorithm in 1969. Although his algorithm is only slightly faster than the standard algorithm for matrix multiplication, he was the first to point out that the standard approach is not optimal. His paper started the search for even faster algorithms such as the more complex Coppersmith–Winograd algorithm of Shmuel Winograd in 1980 (which uses 7 binary multiplications, but 15 binary additions instead of 18 with the Strassen algorithm), published in 1987.
Let A, B be two square matrices over a ring R. We want to calculate the matrix product C as
If the matrices A, B are not of type 2^{n} x 2^{n} we fill the missing rows and columns with zeros.
We partition A, B and C into equally sized block matrices
with
then
With this construction we have not reduced the number of multiplications. We still need 8 multiplications to calculate the C_{i,j} matrices, the same number of multiplications we need when using standard matrix multiplication.
Now comes the important part. We define new matrices
which are then used to express the C_{i,j} in terms of M_{k}. Because of our definition of the M_{k} we can eliminate one matrix multiplication and reduce the number of multiplications to 7 (one multiplication for each M_{k}) and express the C_{i,j} as
We iterate this division process n times until the submatrices degenerate into numbers (elements of the ring R).
Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which they are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. It has been estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations,^{[1]} and 60,000 or more for basic implementations.^{[2]}
The standard matrix multiplication takes approximately 2N^{3} (where N = 2^{n}) arithmetic operations (additions and multiplications); the asymptotic complexity is O(N^{3}).
The number of additions and multiplications required in the Strassen algorithm can be calculated as follows: let f(n) be the number of operations for a matrix. Then by recursive application of the Strassen algorithm, we see that f(n) = 7f(n − 1) + l4^{n}, for some constant l that depends on the number of additions performed at each application of the algorithm. Hence f(n) = (7 + o(1))^{n}, i.e., the asymptotic complexity for multiplying matrices of size N = 2^{n} using the Strassen algorithm is
The reduction in the number of arithmetic operations however comes at the price of a somewhat reduced numerical stability.
