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. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations by or about: Mathematics Look up Mathematics in Wiktionary, the free dictionary Wikimedia Commons has more media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ... Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (or linear spaces), linear transformations, and systems of linear equations. ... Volker Strassen is a German mathematician. ... Flowcharts are often used to represent algorithms. ... This article gives an overview of the various ways to multiply matrices. ...

History

Volker Strassen published the Strassen algorithm in 1969 and although his algorithm is only slightly faster than the standard algorithm for matrix multiplication, he was the first to point out that Gaussian elimination was not optimal. His paper started the search for even faster algorithms (e.g. Coppersmith-Winograd algorithm). 1969 was a common year starting on Wednesday (the link is to a full 1969 calendar). ... In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan (for many, Gaussian elimination is regarded as the front half of the complete Gauss-Jordan elimination), is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining... In the mathematical discipline of linear algebra, the Coppersmith-Winograd algorithm is the fastest currently known algorithm for square matrix multiplication. ...

Algorithm

Let A, B be two square matrices over a field K. We want to calculate the matrix product C as For the square matrix section, see square matrix. ... In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ...

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 In the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a partition of a matrix into rectangular smaller matrices called blocks. ...

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 multiplications for each M_k) and express the C_i,j as

We iterate this division process n-times until the submatrices degenerate into numbers.

Numerical analysis

The standard matrix multiplications takes

multiplications of the elements in the field K. We ignore the additions needed because, depending on K, they can be much faster than the multiplications in computer implementations, especially if the sizes of the matrix entries exceed the word size of the machine. In computer hardware terminology, word size (word length) is the number of bits that a CPU can process at one time (the word). ...

With the Strassen algorithm we can reduce the number of multiplications to

.

External links

• MathWorld: Strassen's Formula

References

• Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969