In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used for matrix multiplication. It is faster than the standard matrix multiplication algorithm and is useful in practice for large matrices, but would be slower than the fastest known algorithm for extremely large matrices.^{[citation needed]}

History

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 published in 1987.

Algorithm

The left column represents 2x2 matrix multiplication. Naïve matrix multiplication requires one multiplication for each "1" of the left column. Each of the other columns represents a single one of the 7 multiplications in the algorithm, and the sum of the columns gives the full matrix multiplication on the left.

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ⁿ x 2ⁿ 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 those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware.

Asymptotic complexity

The standard matrix multiplication takes approximately 2N³ (where N = 2ⁿ) arithmetic operations (additions and multiplications); the asymptotic complexity is O(N³).

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 2ⁿ × 2ⁿ matrix. Then by recursive application of the Strassen algorithm, we see that f(n) = 7f(n-1) + l4ⁿ, for some constant l that depends on the number of additions performed at each application of the algorithm. Hence f(n) = (7 + o(1))ⁿ, i.e., the asymptotic complexity for multiplying matrices of size N = 2ⁿ using the Strassen algorithm is

.

The reduction in the number of arithmetic operations however comes at the price of a somewhat reduced numerical stability.

See also

• Z-order matrix representation
• Karatsuba algorithm, for multiplying n-digit integers in instead of in O(n²) time
• Gauss's complex multiplication algorithm multiplies two complex numbers using 3 real multiplications instead of 4

References

• Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 28: Section 28.2: Strassen's algorithm for matrix multiplication, pp.735–741.

External links

• Weisstein, Eric W., "Strassen's Formulas" from MathWorld. (also includes formulas for fast matrix inversion)
• Tyler J. Earnest, Strassen's Algorithm on the Cell Broadband Engine

• Simple Strassen's algorithms implementation in C (easy for education purposes)

• Simple Strassen's algorithms implementation in Java