Strassenov algoritmus, pomenovaný podľa Volkera Strassena, je algoritmus na násobenie matíc. Oproti štandardnému algoritmu násobiacemu matice priamo podľa vzťahu z definície, s časovou zložitosťou ${\displaystyle O(n^{3})}$, má Strassenov algoritmus o niečo lepšiu asymptotickú časovú zložitosť ${\displaystyle O(N^{\log _{2}7})\approx O(N^{2.81})}$, čo znamená, že pre veľké matice je Strassenov algoritmus rýchlejší, než štandardný algoritmus.

Strassenov algoritmus nie je asymptoticky optimálny. Najrýchlejší známy algoritmus násobenia matíc, tzv. Coppersmithov–Winogradov algoritmus, má časovú zložitosť približne ${\displaystyle O(n^{2.376})}$, ale vzhľadom na veľmi veľký konštantný faktor sa táto výhoda prejaví len pre extrémne veľké matice.

Algoritmus

Nech ${\displaystyle A,B}$ sú matice typu ${\displaystyle 2^{n}\times 2^{n}}$ (v prípade, že matice nie sú typu ${\displaystyle 2^{n}\times 2^{n}}$, je možné doplniť chýbajúce riadky a stĺpce nulami) nad okruhom ${\displaystyle R}$. Označme ${\displaystyle C=A\cdot B}$ súčin týchto matíc. Potom platí

${\displaystyle A=\left,\qquad B=\left\qquad {\textrm {a}}\qquad C=\left,}$

kde ${\displaystyle A_{ij},B_{ij}}$ a ${\displaystyle C_{ij}}$ sú matice typu ${\displaystyle 2^{n-1}\times 2^{n-1}}$, pričom z definície násobenia matíc vyplýva, že platí

${\displaystyle {\begin{array}{rcl}C_{11}&=&A_{11}\cdot B_{11}+A_{12}\cdot B_{21},\\C_{12}&=&A_{11}\cdot B_{12}+A_{12}\cdot B_{22},\\C_{21}&=&A_{21}\cdot B_{11}+A_{22}\cdot B_{21},\\C_{22}&=&A_{21}\cdot B_{12}+A_{22}\cdot B_{22}.\\\end{array}}}$

Štandardný algoritmus možno ekvivalentne prepísať tak, aby násobil matice rekurzívne podľa uvedených vzťahov. Myšlienkou Strassenovho algoritmu je vypočítať hodnoty ${\displaystyle C_{ij}}$ pomocou iných ekvivalentných vzťahov tak, aby bol počet rekurzívnych volaní násobenia matíc menší (v prípade štandardného algoritmu 8 volaní, v prípade Strassenovho algoritmu len 7 volaní). Pri Strassenovom algoritme sa teda hodnoty ${\displaystyle C_{ij}}$ počítajú pomocou tzv. Strassenových vzorcov, ktoré obsahujú len 7 násobení matíc typu ${\displaystyle 2^{n-1}\times 2^{n-1}:}$

${\displaystyle {\begin{array}{rcl}C_{11}&=&M_{1}+M_{2}-M_{4}+M_{6},\\C_{12}&=&M_{4}+M_{5},\\C_{21}&=&M_{6}+M_{7},\\C_{22}&=&M_{2}-M_{3}+M_{5}-M_{7},\\\end{array}}}$

kde

Zdroj:
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---