Strassenov algoritmus

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 $O(n^{3})$, má Strassenov algoritmus o niečo lepšiu asymptotickú časovú zložitosť $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 $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 $A,B$ sú matice typu $2^{n}\times 2^{n}$ (v prípade, že matice nie sú typu $2^{n}\times 2^{n}$, je možné doplniť chýbajúce riadky a stĺpce nulami) nad okruhom $R$. Označme $C=A\cdot B$ súčin týchto matíc. Potom platí

$A=\left[{\begin{array}{cc}A_{11}&A_{12}\\A_{21}&A_{22}\end{array}}\right],\qquad B=\left[{\begin{array}{cc}B_{11}&B_{12}\\B_{21}&B_{22}\end{array}}\right]\qquad {\textrm {a}}\qquad C=\left[{\begin{array}{cc}C_{11}&C_{12}\\C_{21}&C_{22}\end{array}}\right],$

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

${\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 $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 $C_{ij}$ počítajú pomocou tzv. Strassenových vzorcov, ktoré obsahujú len 7 násobení matíc typu $2^{n-1}\times 2^{n-1}:$

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

${\begin{array}{rcl}M_{1}&=&(A_{12}-A_{22})\cdot (B_{21}+B_{22}),\\M_{2}&=&(A_{11}+A_{22})\cdot (B_{11}+B_{22}),\\M_{3}&=&(A_{11}-A_{21})\cdot (B_{11}+B_{12}),\\M_{4}&=&(A_{11}+A_{12})\cdot B_{22},\\M_{5}&=&A_{11}\cdot (B_{12}-B_{22}),\\M_{6}&=&A_{22}\cdot (B_{21}-B_{11}),\\M_{7}&=&(A_{21}+A_{22})\cdot B_{11}.\end{array}}$

Správnosť týchto vzťahov možno overiť úpravou uvedených maticových výrazov.

Pseudokód

Strassenov algoritmus možno zapísať pomocou pseudokódu nasledujúcim spôsobom:

function strassen(A,B,n,min)
    if n < min
       return standard_multiply(A,B)
    else
       m := n / 2
     
       A11 := A[1..m,1..m]
       A12 := A[1..m,m+1..2*m]
       A21 := A[m+1..2*m,1..m]
       A22 := A[m+1..2*m,m+1..2*m]
       B11 := B[1..m,1..m]
       B12 := B[1..m,m+1..2*m]
       B21 := B[m+1..2*m,1..m]
       B22 := B[m+1..2*m,m+1..2*m]
      
       M1 := strassen(A12 - A22,B21 + B22)
       M2 := strassen(A11 + A22,B11 + B22)
       M3 := strassen(A11 - A21,B11 + B12)
       M4 := strassen(A11 + A12,B22)
       M5 := strassen(A11,B12 - B22)
       M6 := strassen(A22,B21 - B11)
       M7 := strassen(A21 + A22,B11)
      
       C11 := M1 + M2 - M4 + M6
       C12 := M4 + M5
       C21 := M6 + M7
       C22 := M2 - M3 + M5 - M7 
      
       init(C)
       C[1..m,1..m] := C11
       C[1..m,m+1..2*m] := C12
       C[m+1..2*m,1..m] := C21
       C[m+1..2*m,m+1..2*m] := C22
     
       return C    
    end.

V uvedenom pseudokóde, A a B sú násobené matice, n je ich rozmer a min je minimálny rozmer matice, pre ktorý sa namiesto Strassenovho algoritmu použije štandardný algoritmus (potrebné na ošetrenie triviálnych prípadov, pri vhodnej voľbe min tiež možno podstatne zlepšiť čas výpočtu).

Časová zložitosť

Nech $T(n)$ je počet aritmetických operácií, ktoré vykoná Strassenov algoritmus počas násobenia matíc typu $n\times n.$ Keďže pre $n\geq 2$ sa pri každom rekurzívnom volaní sa vyvolá presne 7 rekurzívnych volaní násobenia a 18 krát sa použije sčitovanie matíc, ktorého časová zložitosť je pre maticu typu $n\times n$ rovná $n^{2},$ platí rekurentný vzťah

$T(n)=7T\left({\frac {n}{2}}\right)+18\left({\frac {n}{2}}\right)^{2}.$

Pomocou základnej vety o rekurentných vzťahoch (Master theorem) možno vypočítať, že platí

$T(n)=O(N^{\log _{2}7})\approx O(N^{2.81}).$

To znamená, že asymptotická časová zložitosť $T(n)\approx O(N^{2.81})$ je lepšia ako $O(n^{3})$ pri štandardnom algoritme. Výraz $T(n)$ však pri Strassenovom algoritme obsahuje podstatne väčší konštantný faktor, preto v praxi dosahuje Strassenov algoritmus lepší čas ako štandardný algoritmus len pre veľké matice.

Sú známe aj asymptoticky rýchlejšie algoritmy násobenia matíc, ako je Strassenov algoritmus, napr. Coppersmithov–Winogradov algoritmus má časovú zložitosť približne $O(n^{2.376})$. Konštantný faktor v $T(n)$ je však pri takýchto algoritmoch extrémne veľký, čo znamená, že Strassenov algoritmus dosahuje v praxi takmer vždy lepší čas.

Na druhej strane, najlepší známy dolný odhad časovej zložitosti algoritmu na násobenie matíc je $\Omega (n^{2})$. Nie je však známy žiaden algoritmus, ktorý by násobil matice v tomto čase.

Literatúra

• Aho, A. V.; Hopcroft, J. E.; Ullman, J. D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
• Cormen, T. H.; Leiserson, Ch. E.; Rivest, R. L.; Stein, C.: Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill, 2001.
• Golub, G.; van Loan, C.: Matrix computations (3rd ed.). London: The Johns Hopkins University Press, 1996.

Pozri aj

• Karacubov algoritmus

Externé odkazy

• Strassen Formulas - MathWorld (po anglicky).