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=\left(\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right)\text{ és }B=\left(\begin{array}{cc}{b}_{11}& b_{12}\\ b_{21}& b_{22}\end{array}\right)$

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

$C=AB=\left(\begin{array}{cc}{c}_{11}& c_{12}\\ c_{21}& c_{22}\end{array}\right)$

mátrix, ahol
$\begin{array}{c}{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{array}$

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}{cc}{x}_1=(a_{11}+a_{22})(b_{11}+b_{22})& 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}{cc}{c}_{11}=x_1+x_4-x_5+x_7& 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.

$\left(\begin{array}{c}\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\end{array}\right)\cdot \left(\begin{array}{c}\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\end{array}\right)=\left(\begin{array}{c}\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\end{array}\right)$

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}{c}M(0)=1\\ M(k)=7M(k-1),\text{ ha }k>0.\end{array}$

Ennek megoldása

$M(k)=7^k=7^{\log n}=n^{\log 7}\text{ ≈ }{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}{c}A(0)=0\\ A(k)=18(2^{k-1}{)}^2+7A(k-1),\text{ ha }k>0\end{array}$

Innen

$A(k)=6\cdot 7^k-6\cdot 4^k\text{ ≈ }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.