Strassenův algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

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[editovat | editovat zdroj]

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í 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[editovat | editovat zdroj]

Nechť a jsou čtvercové matice nad okruhem , a nechť je jejich součin, tj.

Pokud nejsou matice a řádu , matice se patřičně zvětší a chybějící sloupce a řádky se doplní nulami.

Matice , a rozdělíme na bloky (podmatice) stejného řádu

Prosté rozdělení součinu do bloků počet operací v okruhu neovlivní. Konkrétně vidíme, že pro výpočet všech čtyř bloků je třeba spočítat osm maticových součinů řádu .

Definujeme-li nové matice

můžeme bloky vyjádřit následujícím způsobem

Vidíme, že nyní pro výpočet všech čtyř bloků (samozřejmě včetně sedmi matic ) stačilo spočítat pouze sedm maticových součinů řádu .

Na jednotlivé maticové součiny přitom lze aplikovat stejný postup rekurzivně, dokud se nedostaneme na úroveň matic řádu 1, tedy na čí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[editovat | editovat zdroj]

Standardní multiplikační algoritmus potřebuje

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

.

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

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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[editovat | editovat zdroj]