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

[editovat] 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, jako první upozornil na to, že Gaussova eliminace 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 17) publikovaný roku 1980, nebo složitější Coppersmith–Winogradův algoritmus publikovaný roku 1987.

[editovat] Algoritmus

Nechť A a B jsou čtvercové matice nad okruhem R. Počítáme maticový produkt C jako

$\mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in R^{2^n \times 2^n}$

Pokud nejsou matice A, B typu 2ⁿ x 2ⁿ, vyplníme chybějící sloupce a řádky nulami.

Rozdělíme A, B a C na menší matice stejného řádu

$\mathbf{A} = \begin{bmatrix} \mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\ \mathbf{A}_{2,1} & \mathbf{A}_{2,2} \end{bmatrix} \mbox { , } \mathbf{B} = \begin{bmatrix} \mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\ \mathbf{B}_{2,1} & \mathbf{B}_{2,2} \end{bmatrix} \mbox { , } \mathbf{C} = \begin{bmatrix} \mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\ \mathbf{C}_{2,1} & \mathbf{C}_{2,2} \end{bmatrix}$

$\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in R^{2^{n-1} \times 2^{n-1}}$

$\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}$

$\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}$

$\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}$

$\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2}$

Touto konstrukcí jsme ale počet násobení nesnížili. Stále potřebujeme 8 násobení k nalezení matic C_i,j, stejně jako při použití standardního multiplikačního algoritmu.

Přichází podstatná část. Definujeme si nové matice

$\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})$

$\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}$

$\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})$

$\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})$

$\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}$

$\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})$

$\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})$

které jsou pak použity k vyjádření matic C_i,j pomocí of M_k. Díky naší definici matic M_k můžeme eliminovat jedno násobení matic a vyjádřit C_i,j jako

$\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}$

$\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}$

$\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}$

$\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}$

Iterujeme tímto dělícím procesem n-krát dokud podmatice nedegenerují na čísla.

Praktická implementace Strassenova algoritmu používá pro matice nižších řádů standardní multiplikační postup, pro které je efektivnější. Konkrétní dělící hranice, kdy se Strassenův stává efektivnější než standardní algoritmus, záleží na konkrétní implementaci a hardware.

[editovat] Numerická analýza

Standardní multiplikační algoritmus potřebuje

$n^3 = n^{\log_{2}8}$

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

$n^{\log_{2}7}\approx n^{2.807}$ .

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

[editovat] Reference

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.

[editovat] Externí odkazy

(en)Strassenův algoritmus na MathWorldu

(obsahuje také vzorce pro rychlou inverzi matic)

Tento článek je zčásti nebo zcela založen na překladu článku en:Strassen algorithm na anglické Wikipedii. Číslo revize nebylo určeno.

Kategorie: Lineární algebra | Algoritmy

Strassenův algoritmus v jiných jazycích: Български, Deutsch, English, Français, Bahasa Indonesia, Italiano, 日本語, 한국어, Português, Русский, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Strassen%C5%AFv_algoritmus“
Stránka byla naposledy upravena v Stránka byla naposledy editována 22. 8. 2008 v 20:54.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).