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ť
a
jsou čtvercové matice nad okruhem
, a nechť
je jejich součin, tj.
![{\displaystyle {\boldsymbol {C}}={\boldsymbol {A}}{\boldsymbol {B}}\qquad {\boldsymbol {A}},{\boldsymbol {B}},{\boldsymbol {C}}\in R^{2^{n}\times 2^{n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30cc456e059c3903ba4d01abf51a69cd1d1a8ed2)
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
:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31606e85f7a1706dbfd348b188cf8f03e05e0001)
![{\displaystyle {\boldsymbol {A}}_{ij},{\boldsymbol {B}}_{ij},{\boldsymbol {C}}_{ij}\in R^{2^{n-1}\times 2^{n-1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2a583f399865ee47a8dd253153526bf4e69d04d)
![{\displaystyle {\boldsymbol {C}}_{11}={\boldsymbol {A}}_{11}{\boldsymbol {B}}_{11}+{\boldsymbol {A}}_{12}{\boldsymbol {B}}_{21}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed0863aa4a6a036d42a3281c955d45c37340853d)
![{\displaystyle {\boldsymbol {C}}_{12}={\boldsymbol {A}}_{11}{\boldsymbol {B}}_{12}+{\boldsymbol {A}}_{12}{\boldsymbol {B}}_{22}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19f01bb9977191b7c76dceec897ded34dd9181b3)
![{\displaystyle {\boldsymbol {C}}_{21}={\boldsymbol {A}}_{21}{\boldsymbol {B}}_{11}+{\boldsymbol {A}}_{22}{\boldsymbol {B}}_{21}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fbbec06a56500e16f6c79d2b350782e86d019d0)
![{\displaystyle {\boldsymbol {C}}_{22}={\boldsymbol {A}}_{21}{\boldsymbol {B}}_{12}+{\boldsymbol {A}}_{22}{\boldsymbol {B}}_{22}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af32e6330fdca25bd5022e0553cfa371fc24019e)
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
![{\displaystyle {\boldsymbol {M}}_{1}=({\boldsymbol {A}}_{11}+{\boldsymbol {A}}_{22})({\boldsymbol {B}}_{11}+{\boldsymbol {B}}_{22})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bdb8db2792f84b80a257c5c91cb1c86ce4ec9dbf)
![{\displaystyle {\boldsymbol {M}}_{2}=({\boldsymbol {A}}_{21}+{\boldsymbol {A}}_{22}){\boldsymbol {B}}_{11}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3dbc6c11218bf7150c5932e7c463172d6464803d)
![{\displaystyle {\boldsymbol {M}}_{3}={\boldsymbol {A}}_{11}({\boldsymbol {B}}_{12}-{\boldsymbol {B}}_{22})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02e346c0b0a21c82a330da173b53a130e6171c7a)
![{\displaystyle {\boldsymbol {M}}_{4}={\boldsymbol {A}}_{22}({\boldsymbol {B}}_{21}-{\boldsymbol {B}}_{11})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b20b525b0cf76352b1773414229a3f7cf4dbaa6)
![{\displaystyle {\boldsymbol {M}}_{5}=({\boldsymbol {A}}_{11}+{\boldsymbol {A}}_{12}){\boldsymbol {B}}_{22}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffce31deacd8e2ed840dc4fb084e778c23ce0d7f)
![{\displaystyle {\boldsymbol {M}}_{6}=({\boldsymbol {A}}_{21}-{\boldsymbol {A}}_{11})({\boldsymbol {B}}_{11}+{\boldsymbol {B}}_{12})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c14a24357de8b00e56483dddd812fedcef6c5e41)
![{\displaystyle {\boldsymbol {M}}_{7}=({\boldsymbol {A}}_{12}-{\boldsymbol {A}}_{22})({\boldsymbol {B}}_{21}+{\boldsymbol {B}}_{22})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43240fba6e82e4e4a6217f214e97584a504272ec)
lze bloky
vyjádřit následujícím způsobem
![{\displaystyle {\boldsymbol {C}}_{11}={\boldsymbol {M}}_{1}+{\boldsymbol {M}}_{4}-{\boldsymbol {M}}_{5}+{\boldsymbol {M}}_{7}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ebb0a575b824f15deae8f5431c97d26d8b187c6)
![{\displaystyle {\boldsymbol {C}}_{12}={\boldsymbol {M}}_{3}+{\boldsymbol {M}}_{5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48d81f59b00bc6b0c3132ab81f88b14efed238a4)
![{\displaystyle {\boldsymbol {C}}_{21}={\boldsymbol {M}}_{2}+{\boldsymbol {M}}_{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2458466a88a3f1740d1eb5a91d8c9a292777f49)
![{\displaystyle {\boldsymbol {C}}_{22}={\boldsymbol {M}}_{1}-{\boldsymbol {M}}_{2}+{\boldsymbol {M}}_{3}+{\boldsymbol {M}}_{6}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4954cb9cba02eb41ea278a97b02439258195c14a)
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
![{\displaystyle n^{3}=n^{\log _{2}8}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ef3bd44bb8fa3c3ba37484dd1e8684216dea7aa)
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
- Strassenův algoritmus v encyklopedii MathWorld (anglicky) (obsahuje také vzorce pro rychlou inverzi matic)
Portály: Matematika