Street algorithm

The Strassen algorithm (invented by the German mathematician Volker Strassen ) is an algorithm from linear algebra and is used for matrix multiplication . The Strassen algorithm realizes the matrix multiplication asymptotically more efficiently than the standard method and is in practice faster for large matrices (those with a rank greater than 1000).

The algorithm

To simplify matters, the special case of square matrices with rows or columns is considered. ${\displaystyle 2^{k}}$

So be matrices over a ring and also be their product . These can also be used as block matrices ${\displaystyle A,B\in R^{2^{k}\times 2^{k}}}$ ${\displaystyle R}$ ${\displaystyle C=A\cdot B\in R^{2^{k}\times 2^{k}}}$

${\displaystyle A={\begin{pmatrix}A_{1,1}&A_{1,2}\\A_{2,1}&A_{2,2}\end{pmatrix}},\qquad B={\begin{pmatrix}B_{1,1}&B_{1,2}\\B_{2,1}&B_{2,2}\end{pmatrix}},\qquad C={\begin{pmatrix}C_{1,1}&C_{1,2}\\C_{2,1}&C_{2,2}\end{pmatrix}}}$

consider where are. ${\displaystyle A_{i,j},B_{i,j},C_{i,j}\in R^{2^{k-1}\times 2^{k-1}}}$

The following applies to the multiplication of block matrices:

${\displaystyle C_{1,1}=A_{1,1}\cdot B_{1,1}+A_{1,2}\cdot B_{2,1}}$

${\displaystyle C_{1,2}=A_{1,1}\cdot B_{1,2}+A_{1,2}\cdot B_{2,2}}$

${\displaystyle C_{2,1}=A_{2,1}\cdot B_{1,1}+A_{2,2}\cdot B_{2,1}}$

${\displaystyle C_{2,2}=A_{2,1}\cdot B_{1,2}+A_{2,2}\cdot B_{2,2}}$

The direct calculation of the requires (complex) matrix multiplications. To reduce this number, Strassen's algorithm calculates the following auxiliary matrices: ${\displaystyle C_{i,j}}$ ${\displaystyle 8}$

${\displaystyle M_{1}:=(A_{1,1}+A_{2,2})\cdot (B_{1,1}+B_{2,2})}$

${\displaystyle M_{2}:=(A_{2,1}+A_{2,2})\cdot B_{1,1}}$

${\displaystyle M_{3}:=A_{1,1}\cdot (B_{1,2}-B_{2,2})}$

${\displaystyle M_{4}:=A_{2,2}\cdot (B_{2,1}-B_{1,1})}$

${\displaystyle M_{5}:=(A_{1,1}+A_{1,2})\cdot B_{2,2}}$

${\displaystyle M_{6}:=(A_{2,1}-A_{1,1})\cdot (B_{1,1}+B_{1,2})}$

${\displaystyle M_{7}:=(A_{1,2}-A_{2,2})\cdot (B_{2,1}+B_{2,2})}$

Only multiplications are necessary to calculate the , which can now be determined by additions (and subtractions): ${\displaystyle M_{i}}$ ${\displaystyle 7}$ ${\displaystyle C_{ij}}$

${\displaystyle C_{1,1}=M_{1}+M_{4}-M_{5}+M_{7}}$

${\displaystyle C_{1,2}=M_{3}+M_{5}}$

${\displaystyle C_{2,1}=M_{2}+M_{4}}$

${\displaystyle C_{2,2}=M_{1}-M_{2}+M_{3}+M_{6}}$

For the multiplications in the calculation of the above procedure is carried out recursively until the problem is reduced to the multiplication of scalars. ${\displaystyle M_{i}}$

In practice, normal multiplication can be faster for small matrices. Therefore, a change to the usual multiplication instead of a recursive call makes sense as soon as the matrix dimensions are small enough (cut-off).

The left column represents a matrix multiplication . Every other column represents one of the multiplications of the Strassen algorithm. ${\displaystyle 2\times 2}$ ${\displaystyle 7}$

effort

The standard algorithm for matrix multiplication is required

${\displaystyle n^{\log _{2}8}=n^{3}}$

Multiplications of the elements of the ring R . We ignore the additions needed because, depending on R , they can be much faster than the multiplications in computer implementations. With the Strassen algorithm we can calculate the number of multiplications

${\displaystyle n^{\log _{2}7}\approx n^{2,807}}$

to reduce. The reduction in the number of multiplications, however, is paid for with a reduction in numerical stability .

literature

• Volker Strassen: Gaussian Elimination is not Optimal . In: Numerische Mathematik , Volume 13, 1969, pp. 354-356, ISSN  0029-599X , doi: 10.1007 / BF02165411 .

Web links

• Eric W. Weisstein : Strassen's Formulas . In: MathWorld (English).

Individual evidence

1. ^ Webb Miller: Computational complexity and numerical stability . (PDF) In: SIAM News . 4, 1975, pp. 97-107.