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

HistorieEditovat

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.

AlgoritmusEditovat

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ělící hranice, kdy se Strassenův stává efektivnější než standardní algoritmus, záleží na konkrétní implementaci a hardware.

Numerická analýzaEditovat

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.

OdkazyEditovat

ReferenceEditovat

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í odkazyEditovat