Strassenův algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledá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, 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 18) publikovaný roku 1980, nebo složitější Coppersmith–Winogradův algoritmus publikovaný roku 1987.

Algoritmus[editovat | editovat zdroj]

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 2n x 2n, matice se patřičně zvětší a chybějící sloupce a řádky se doplní nulami.

Matice A, B a C se rozdělí 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}

I po této úpravě zůstává počet násobení stejný. Stále je třeba 8 násobení k nalezení matic Ci,j.

Přichází podstatná část. Definujme 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 Ci,j pomocí Mk. Díky definici matic Mk lze eliminovat jedno násobení matic a vyjádřit Ci,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}

Na jednotlivá násobení matic lze rekurzivně aplikovat stejný algoritmus, 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ší. 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ýza[editovat | editovat zdroj]

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.

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]