Strassen-algoritmus

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

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

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)=7M(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.

Források

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