Strassenův algoritmus

Strassenův algoritmus (pojmenovaný po německém matematikovi Volkeru Strassenovi) je algoritmus používaný pro násobení matic. Byl prvním asymptoticky subkubickým algoritmem pro násobení matic (kubickou složitost má klasický naivní algoritmus, tj. násobení pomocí definičního vztahu pro součin matic). Byl objeven roku 1969, ale od roku 1978 se objevila řada algoritmů s výrazně lepší asymptotickou složitostí, jeden z nich byl navržen i V. Strassenem. Výrazným průlomem byl Coppersmithův-Winogradův algoritmus z roku 1990, ale i ten byl již překonán. Na rozdíl od dalších algoritmů je ale Strassenův algoritmus vhodný pro praktické použití, protože je nejrychlejším algoritmem pro matice, které se v reálných výpočtech objevují (s výjimkou úplně malých matic o maximálně několika desítkách řádků, kde je rychlejší klasický naivní algoritmus).

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í. +more 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

Literatura

Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. +more 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. . Chapter 28: Sekce 28. 2: Strassen's algorithm for matrix multiplication, pp. 735-741.

Externí odkazy

(obsahuje také vzorce pro rychlou inverzi matic)

Kategorie:Teorie matic Kategorie:Algoritmy