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.

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

${\displaystyle 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

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

mátrix, ahol
${\displaystyle {\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 ${\displaystyle C}$ mátrix kiszámítására az, hogy a fenti 8 szorzás helyett 7-et használjon. Ha

${\displaystyle {\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

${\displaystyle {\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 ${\displaystyle n=2^{k}}$. Felosztjuk a mátrixokat ${\displaystyle {\frac {n}{2}}\times {\frac {n}{2}}}$ típusú mátrixokra, és alkalmazzuk Strassen módszerét ezen mátrixok szorzására is.

${\displaystyle {\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.

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

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

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

Ennek megoldása

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

A klasszikus mátrixszorzás esetében a szorzások száma ${\displaystyle n^{3}}$, a Strassen-algoritmus esetében, ha ${\displaystyle n=2^{k}}$, akkor a szorzások száma lecsökkenthető ${\displaystyle 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

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

Innen

${\displaystyle 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 ${\displaystyle n^{3}-n^{2}}$.

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

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