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ť 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.
Algoritmus využívá rozdělení matic
, a na bloky (podmatice) řádu :
Prosté rozdělení součinu do bloků počet operací v okruhu neovlivní. Pro výpočet všech čtyř bloků je třeba spočítat osm maticových součinů řádu .
S pomocí nových matic
lze bloky vyjádřit následujícím způsobem
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 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
jednotlivých součinů v okruhu . 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
-
.
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í 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
Zdroj
Poslední aktualizace obsahu: 2023-12-15 22:38:20
Zdroj: Wikipedia (autoři článku Strassenův algoritmus)
Licence textu: CC-BY-SA-3.0 Unported
Tento článek byl automaticky přejat z Wikipedie. Na obrázcích nebyly provedeny žádné změny. Obrázky se zobrazují ve zmenšené velikosti (jako miniatury). Kliknutím na obrázek získáte další informace o autorovi a licenci. Byly změněny prvky designu, odstraněny některé odkazy specifické pro Wikipedii (např. odkazy na Editaci a nebo na neexistující hesla) a provedena optimalizace pro rychlé načítání.