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

Algoritmus

Nechť ${\boldsymbol {A}}$ a ${\boldsymbol {B}}$ jsou čtvercové matice nad okruhem $R$, a nechť ${\boldsymbol {C}}$ je jejich součin, tj.

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

Pokud nejsou matice ${\boldsymbol {A}}$ a ${\boldsymbol {B}}$ řádu $2^{n}$, matice se patřičně zvětší a chybějící sloupce a řádky se doplní nulami.

Algoritmus využívá rozdělení matic ${\boldsymbol {A}}$, ${\boldsymbol {B}}$ a ${\boldsymbol {C}}$ na bloky (podmatice) řádu $2^{n-1}$:

${\boldsymbol {A}}={\begin{pmatrix}{\boldsymbol {A}}_{11}&{\boldsymbol {A}}_{12}\\{\boldsymbol {A}}_{21}&{\boldsymbol {A}}_{22}\end{pmatrix}}{\mbox{ , }}{\boldsymbol {B}}={\begin{pmatrix}{\boldsymbol {B}}_{11}&{\boldsymbol {B}}_{12}\\{\boldsymbol {B}}_{21}&{\boldsymbol {B}}_{22}\end{pmatrix}}{\mbox{ , }}{\boldsymbol {C}}={\begin{pmatrix}{\boldsymbol {C}}_{11}&{\boldsymbol {C}}_{12}\\{\boldsymbol {C}}_{21}&{\boldsymbol {C}}_{22}\end{pmatrix}}$

${\boldsymbol {A}}_{ij},{\boldsymbol {B}}_{ij},{\boldsymbol {C}}_{ij}\in R^{2^{n-1}\times 2^{n-1}}$

${\boldsymbol {C}}_{11}={\boldsymbol {A}}_{11}{\boldsymbol {B}}_{11}+{\boldsymbol {A}}_{12}{\boldsymbol {B}}_{21}$

${\boldsymbol {C}}_{12}={\boldsymbol {A}}_{11}{\boldsymbol {B}}_{12}+{\boldsymbol {A}}_{12}{\boldsymbol {B}}_{22}$

${\boldsymbol {C}}_{21}={\boldsymbol {A}}_{21}{\boldsymbol {B}}_{11}+{\boldsymbol {A}}_{22}{\boldsymbol {B}}_{21}$

${\boldsymbol {C}}_{22}={\boldsymbol {A}}_{21}{\boldsymbol {B}}_{12}+{\boldsymbol {A}}_{22}{\boldsymbol {B}}_{22}$

Prosté rozdělení součinu do bloků počet operací v okruhu $R$ neovlivní. Pro výpočet všech čtyř bloků ${\boldsymbol {C}}_{ij}$ je třeba spočítat osm maticových součinů řádu $2^{n-1}$.

S pomocí nových matic

${\boldsymbol {M}}_{1}=({\boldsymbol {A}}_{11}+{\boldsymbol {A}}_{22})({\boldsymbol {B}}_{11}+{\boldsymbol {B}}_{22})$

${\boldsymbol {M}}_{2}=({\boldsymbol {A}}_{21}+{\boldsymbol {A}}_{22}){\boldsymbol {B}}_{11}$

${\boldsymbol {M}}_{3}={\boldsymbol {A}}_{11}({\boldsymbol {B}}_{12}-{\boldsymbol {B}}_{22})$

${\boldsymbol {M}}_{4}={\boldsymbol {A}}_{22}({\boldsymbol {B}}_{21}-{\boldsymbol {B}}_{11})$

${\boldsymbol {M}}_{5}=({\boldsymbol {A}}_{11}+{\boldsymbol {A}}_{12}){\boldsymbol {B}}_{22}$

${\boldsymbol {M}}_{6}=({\boldsymbol {A}}_{21}-{\boldsymbol {A}}_{11})({\boldsymbol {B}}_{11}+{\boldsymbol {B}}_{12})$

${\boldsymbol {M}}_{7}=({\boldsymbol {A}}_{12}-{\boldsymbol {A}}_{22})({\boldsymbol {B}}_{21}+{\boldsymbol {B}}_{22})$

lze bloky ${\boldsymbol {C}}_{ij}$ vyjádřit následujícím způsobem

${\boldsymbol {C}}_{11}={\boldsymbol {M}}_{1}+{\boldsymbol {M}}_{4}-{\boldsymbol {M}}_{5}+{\boldsymbol {M}}_{7}$

${\boldsymbol {C}}_{12}={\boldsymbol {M}}_{3}+{\boldsymbol {M}}_{5}$

${\boldsymbol {C}}_{21}={\boldsymbol {M}}_{2}+{\boldsymbol {M}}_{4}$

${\boldsymbol {C}}_{22}={\boldsymbol {M}}_{1}-{\boldsymbol {M}}_{2}+{\boldsymbol {M}}_{3}+{\boldsymbol {M}}_{6}$

Pro výpočet všech čtyř bloků ${\boldsymbol {C}}_{ij}$ (samozřejmě včetně sedmi matic ${\boldsymbol {M}}_{l}$) stačilo spočítat pouze sedm maticových součinů řádu $2^{n-1}$.

Na jednotlivé maticové součiny přitom lze aplikovat stejný postup rekurentně až na úroveň matic řádu 1, tedy na jednotlivá čísla.

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

Numerická analýza

Standardní algoritmus podle definice maticového součinu potřebuje určit

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

jednotlivých součinů v okruhu $R$. Ignorujeme složitost součtu 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).

Strassenův algoritmus sníží počet součinů na

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

Nižší počet součinů je za cenu snížené numerické stability.

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ý vedl k objevu Winogradova algoritmu publikovaného roku 1980 (stejně jako Strassenův používá 7 součinů, ale 15 součtů namísto 18), nebo složitějšího Coppersmithova–Winogradova algoritmu publikovaného roku 1987.

Odkazy

Reference

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

Literatura

• 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