Strassen-algoritmus

A Wikipédiából, a szabad enciklopédiából

A Strassen-algoritmus négyzetes mátrixok szorzását a klasszikus mátrixszorzásnál kevesebb szorzással oldja meg. 1969-ben írta le Volker Strassen német matematikus.

Az algoritmus alapötlete és leírása[szerkesztés | forrásszöveg szerkesztése]

Mátrixszorzás illusztrálása. Például: az A mátrix első sora szorozva a B mátrix második oszlopával, megadja a C mátrix c_{12} elemét.

2×2-es mátrixok klasszikus szorzása a következőképpen valósítható meg. Legyen


A =
\begin{pmatrix}
a_{11} & a_{12} \\
a_{21} & a_{22}
\end{pmatrix}
\mbox { és }
B =
\begin{pmatrix}
b_{11} & b_{12} \\
b_{21} & b_{22}
\end{pmatrix}

a két összeszorzandó mátrix. A szorzás eredménye a


C = AB =
\begin{pmatrix}
c_{11} & c_{12} \\
c_{21} & c_{22}
\end{pmatrix}

mátrix, ahol

\begin{matrix}
c_{11} = a_{11}b_{11}+a_{12}b_{21}\\

c_{12} = a_{11}b_{12}+a_{12}b_{22}\\

c_{21} = a_{21}b_{11}+a_{22}b_{21}\\

c_{22} = a_{21}b_{12}+a_{22}b_{22}
\end{matrix}

Strassen ötlete a C mátrix kiszámítására az, hogy a fenti 8 szorzás helyett 7-et használjon. Ha


\begin{array}{ll}
x_1=(a_{11}+a_{22})(b_{11}+b_{22}) \quad & x_5=(a_{11}+a_{12})b_{22}\\
x_2=(a_{21}+a_{22})b_{11} & x_6=(a_{21}-a_{11})(b_{11}+b_{12})\\
x_3=a_{11}(b_{12}-b_{22}) & x_7=(a_{12}-a_{22})(b_{21}+b_{22})\\
x_4=a_{22}(b_{21}-b_{11}) &
\end{array}

akkor egyszerű számítással bizonyítható, hogy


\begin{array}{ll}
c_{11}= x_1+x_4-x_5+x_7 \qquad & c_{12}=x_3+x_5\\
c_{21}= x_2+x_4 & c_{22}=x_1+x_3-x_2+x_6
\end{array}

Ebben az esetben az összeadások száma viszont 18-ra nő.

Legyen  n=2^k . Felosztjuk a mátrixokat \frac{n}{2} \times\frac{n}{2} típusú mátrixokra, és alkalmazzuk Strassen módszerét ezen mátrixok szorzására is.


\begin{pmatrix}
\begin{array}{c|c}
A_{11} & A_{12}\\ \hline
A_{21} & A_{22}
\end{array}
\end{pmatrix}
\cdot
\begin{pmatrix}
\begin{array}{c|c}
B_{11} & B_{12}\\ \hline
B_{21} & B_{22}
\end{array}
\end{pmatrix}
=
\begin{pmatrix}
\begin{array}{c|c}
C_{11} & C_{12}\\ \hline
C_{21} & C_{22}
\end{array}
\end{pmatrix}

Ezt a felbontást addig végezzük, ameddig csak lehet, és minden esetben alkalmazzuk a Strassen elképzelését mátrixok szorzására, függetlenül attól, hogy elemei mátrixok vagy számok.

Az algoritmus elemzése[szerkesztés | forrásszöveg szerkesztése]

Ha  n=2^k , akkor legyen M(k) a szorzások száma, A(k) pedig az összeadások száma.

Felírhatjuk a következő rekurzív összefüggéseket


\begin{array}{l}
M(0)=1\\
M(k)=7 M(k\!-\!1), \mbox{ ha } k>0.
\end{array}

Ennek megoldása


M(k) = 7^{k} = 7^{\log n} = n^{\log 7} \mbox{ ≈ } n^{2,81}
        (A \log itt a kettes alapú logaritmust jelöli.)

A klasszikus mátrixszorzás esetében a szorzások száma n^3 , a Strassen-algoritmus esetében, ha  n=2^k , akkor a szorzások száma lecsökkenthető  n^{2,81}-re. Ez az eredmény elméleti szempontból fontos, mivel a kitevő értékét 3 alá csökkentette.

Hasonló módon számítható ki az összeadások száma


\begin{array}{l}
A(0)=0\\
A(k)=18(2^{k-1})^2+ 7A(k-1), \mbox{ ha } k>0
\end{array}

Innen


A(k) = 6 \cdot 7^k - 6\cdot 4^k \mbox{ ≈ } 6n^{2,81}-6n^2

A klasszikus mátrixszorzás esetében az összeadások száma  n^3-n^2 .

Ma már létezik ennél is gyorsabb algoritmus, az ún. Coppersmith–Winograd-algoritmus, amely kb.  n^{2,37} szorzást igényel.[1]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. Coppersmith, Don; Winograd, Shmuel: "Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation 9 (3): 1990, p.251. Online hozzáférés

Források[szerkesztés | forrásszöveg szerkesztése]

  • Sara Baase: Computer Algorithms. Introduction to Design and Analysis, Addison-Wesley Publishing Company, 1983.
  • T. H. Cormen, C. E. Leiserson, R. R. Rivest, C. Stein, Új algoritmusok, Scolar Kiadó, Budapest, 2003.