Strassenov algoritem

Iz MaFiRaWiki

Strassenovo množenje matrik je postopek tipa deli in vladaj za množenje matrik, ki zahteva O(n^{\log_2 7}) množenj namesto običajnih O(n3).

Naj bosta A in B kvadratni matriki velikosti 2n \times 2n (če dimenzija ni sodo število, dopišemo eno prazno vrstico in stolpec). Njun zmnožek C = A \times B izračunamo z bločnimi matrikami:

A = \begin{bmatrix} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{bmatrix} \mbox { , } B = \begin{bmatrix} B_{1,1} & B_{1,2} \\ B_{2,1} & B_{2,2} \end{bmatrix} \mbox { , } C = \begin{bmatrix} C_{1,1} & C_{1,2} \\ C_{2,1} & C_{2,2} \end{bmatrix}

kjer so matrike Ai,j, Bi,j in Ci,j velikosti n \times n in velja

C1,1 = A1,1B1,1 + A1,2B2,1
C1,2 = A1,1B1,2 + A1,2B2,2
C2,1 = A2,1B1,1 + A2,2B2,1
C2,2 = A2,1B1,2 + A2,2B2,2

Vendar računanje matrik Ci,j z zgornjimi enačbami ne prinese nobenega izboljšanja. Strassenov algoritem jih izračuna tako, da prihrani eno bločno množenje: naj bodo

M1 = (A1,1 + A2,2)(B1,1 + B2,2)
M2 = (A2,1 + A2,2)B1,1
M3 = A1,1(B1,2B2,2)
M4 = A2,2(B2,1B1,1)
M5 = (A1,1 + A1,2)B2,2
M6 = (A2,1A1,1)(B1,1 + B1,2)
M7 = (A1,2A2,2)(B2,1 + B2,2)

V matrikah Mi imamo 7 bločnih množenj namesto 8, kot v zgornji definiciji matrik Ci,j. Matrike Ci,j izračunamo takole:

C1,1 = M1 + M4M5 + M7
C1,2 = M3 + M5
C2,1 = M2 + M4
C2,2 = M1M2 + M3 + M6

Učinkovitost algoritma

Strassenov postopek ima časovno zahtevnost O(n^{\log_2 7}), kar je približno O(n2.81) in je bolje od naivnega postopka, ki ima zahtevnost O(n3). Vendar se v praksi Strassenovo množenje za majhne matrike ne izplača, zato Strassenov postopek ustavimo, ko so bločne matrike zadosti majhne.

Glej tudi

Viri

Osebna orodja