Хэрэглэгч:Timur/Ноорог/Штрассений алгоритм

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.

Түүх

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 Gaussian elimination is not optimal. His paper started the search for even faster algorithms such as the Winograd algorithm in 1980 (which uses 7 binary multiplications, but 15 binary additions instead of 18 with the Strassen algorithm), and the more complex Coppersmith-Winograd algorithm published in 1987.

Алгоритм

A ба B нь R цагираг дээрх матрицууд бөгөөд тэдгээрийн үржвэр нь C болог:

$\mathbf {C} =\mathbf {A} \mathbf {B} ,\qquad \mathbf {A} ,\mathbf {B} ,\mathbf {C} \in R^{2^{n}\times 2^{n}}$

Хэрэв A ба B матрицуудын мөр баганын тоо 2ⁿ биш бол бид тохирох тооны тэг мөр баганууд нэмэх замаар ийм хэмжээтэй болгож болно.

A, B ба C матрицуудыг тэнцүү хэмжээтэй блок матрицуудад хуваая:

$\mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1,1}&\mathbf {A} _{1,2}\\\mathbf {A} _{2,1}&\mathbf {A} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {B} ={\begin{bmatrix}\mathbf {B} _{1,1}&\mathbf {B} _{1,2}\\\mathbf {B} _{2,1}&\mathbf {B} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {C} ={\begin{bmatrix}\mathbf {C} _{1,1}&\mathbf {C} _{1,2}\\\mathbf {C} _{2,1}&\mathbf {C} _{2,2}\end{bmatrix}}$

үүнд

$\mathbf {A} _{i,j},\mathbf {B} _{i,j},\mathbf {C} _{i,j}\in R^{2^{n-1}\times 2^{n-1}}.$

Тэгвэл

$\mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1}$

$\mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2}$

$\mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1}$

$\mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2}$

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

$\mathbf {M} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})$

$\mathbf {M} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1}$

$\mathbf {M} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})$

$\mathbf {M} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})$

$\mathbf {M} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2}$

$\mathbf {M} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})$

$\mathbf {M} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})$

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

$\mathbf {C} _{1,1}=\mathbf {M} _{1}+\mathbf {M} _{4}-\mathbf {M} _{5}+\mathbf {M} _{7}$

$\mathbf {C} _{1,2}=\mathbf {M} _{3}+\mathbf {M} _{5}$

$\mathbf {C} _{2,1}=\mathbf {M} _{2}+\mathbf {M} _{4}$

$\mathbf {C} _{2,2}=\mathbf {M} _{1}-\mathbf {M} _{2}+\mathbf {M} _{3}+\mathbf {M} _{6}$

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

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.

Тоон анализ

The standard matrix multiplications takes

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

multiplications of the elements in the ring R. We ignore the additions needed because, depending on R, 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.

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

$n^{\log _{2}7}\approx n^{2.807}$.

The reduction in the number of multiplications however comes at the price of a somewhat reduced numeric stability.

Ном хэвлэл

• 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.