Strassenův algoritmus

Strassenův algoritmus (pojmenovaný po německém matematikovi Volkeru Strassenovi) je algoritmus používaný pro násobení matic. Je asymptoticky rychlejší než standardní multiplikační algoritmus, ale pomalejší než nejrychlejší známý algoritmus (Coppersmith–Winogradův algoritmus). Používá se zejména pro matice vysokých řádů.

Historie

Volker Strassen publikoval svůj algoritmus v roce 1969. Přestože je jeho algoritmus jen mírně rychlejší než standardní multiplikační algoritmus, svou publikací jako první upozornil na to, že tento standardní algoritmus se složitostí $\Theta ({n}^{3})$ není optimální. Jeho práce iniciovala další výzkum v této oblasti, který vyprodukoval například Winogradův algoritmus (který stejně jako Strassen používá 7 binárních násobení, ale 15 binárních sčítání místo 18) publikovaný roku 1980, nebo složitější Coppersmith–Winogradův algoritmus publikovaný roku 1987.

Algoritmus

Nechť A a B jsou čtvercové matice nad okruhem R. Počítáme maticový produkt C jako

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

Pokud nejsou matice A, B typu 2ⁿ x 2ⁿ, matice se patřičně zvětší a chybějící sloupce a řádky se doplní nulami.

Matice A, B a C se rozdělí na menší matice stejného řádu

$\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}$

I po této úpravě zůstává počet násobení stejný. Stále je třeba 8 násobení k nalezení matic C_i,j.

Přichází podstatná část. Definujme nové matice:

$\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})$

které jsou pak použity k vyjádření matic C_i,j pomocí M_k. Díky definici matic M_k lze eliminovat jedno násobení matic a vyjádřit C_i,j jako

$\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}$

Na jednotlivá násobení matic lze rekurzivně aplikovat stejný algoritmus, dokud podmatice nedegenerují na čísla.

Praktická implementace Strassenova algoritmu používá pro matice nižších řádů standardní multiplikační postup, pro které je efektivnější. Dělící hranice, kdy se Strassenův stává efektivnější než standardní algoritmus, záleží na konkrétní implementaci a hardware.

Numerická analýza

Standardní multiplikační algoritmus potřebuje

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

násobení v okruhu R. Ignorujeme sčítání matic, protože sčítání je pro vyšší řády matice mnohem rychlejší než násobení (s rostoucím řádem matic tento rozdíl dále roste).

Se Strassenovým algoritmem tak můžeme snížit počet násobení na

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

Nižší počet násobení však získáváme za cenu snížené numerické stability.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Strassen algorithm na anglické Wikipedii.

• 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, druhé vydání. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 28: Sekce 28.2: Strassen's algorithm for matrix multiplication, pp.735–741.

Externí odkazy

• Strassenův algoritmus v encyklopedii MathWorld (anglicky) (obsahuje také vzorce pro rychlou inverzi matic)

Portály: Matematika