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 formula_1, má Strassenov algoritmus o niečo lepšiu asymptotickú časovú zložitosť formula_2, č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 formula_3, 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 formula_4 sú matice typu formula_5 (v prípade, že matice nie sú typu formula_5, je možné doplniť chýbajúce riadky a stĺpce nulami) nad okruhom formula_7. Označme formula_8 súčin týchto matíc. Potom platí
kde formula_10 a formula_11 sú matice typu formula_12, pričom z definície násobenia matíc vyplýva, že platí
Š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 formula_11 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 formula_11 počítajú pomocou tzv. Strassenových vzorcov, ktoré obsahujú len 7 násobení matíc typu formula_16
kde
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 &lt; 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 formula_19 je počet aritmetických operácií, ktoré vykoná Strassenov algoritmus počas násobenia matíc typu formula_20 Keďže pre formula_21 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 formula_22 rovná formula_23 platí rekurentný vzťah
Pomocou základnej vety o rekurentných vzťahoch ("Master theorem") možno vypočítať, že platí
To znamená, že asymptotická časová zložitosť formula_26 je lepšia ako formula_1 pri štandardnom algoritme. Výraz formula_19 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 formula_3. Konštantný faktor v formula_19 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 formula_31. Nie je však známy žiaden algoritmus, ktorý by násobil matice v tomto čase.