Strassenovo množenje matrik

Iz MaFiRaWiki

Vsebina

Množenje matrik

Množenje dveh matrik je izvedljivo le, če je število stolpcev prve matrike enako številu vrstic druge matrike. Če je A matrika razsežnosti m-krat-n, (m vrstic, n stolpcev) in je B matrika razsežnosti n-krat-p (n vrstic, p stolpcev), potem je njun produkt AB matrika razsežnosti m-krat-p (m vrstic, p stolpcev) definiran kot:

(AB)[i, j] = A[i, 1] * B[1, j] + A[i, 2] * B[2, j] + ... + A[i, n] * B[n, j] za vsak par i in j.

Primer

\begin{bmatrix}     1 & 0 & 2 \\     -1 & 3 & 1 \\   \end{bmatrix} \times   \begin{bmatrix}     3 & 1 \\     2 & 1 \\     1 & 0   \end{bmatrix} =   \begin{bmatrix}      (1 \times 3  +  0 \times 2  +  2 \times 1) & (1 \times 1   +   0 \times 1   +   2 \times 0) \\     (-1 \times 3  +  3 \times 2  +  1 \times 1) & (-1 \times 1   +   3 \times 1   +   1 \times 0) \\   \end{bmatrix} =   \begin{bmatrix}     5 & 1 \\     4 & 2 \\   \end{bmatrix}

To množenje ima sledeče lastnosti:

  • (AB)C = A(BC) za vse k-krat-m matrike A, m-krat-n matrike B in n-krat-p matrike C ("asociativnost").
  • (A + B)C = AC + BC za vse m-krat-n matrike A in B in n-by-k matrike C ("distributivnost").
  • C(A + B) = CA + CB za vse m-krat-n matrike A in B in k-krat-m matrike C ("distributivnost").

Pomembno se je zavedati, da komutativnost ne velja vedno. Splošno torej za matriki A in B in njun produkt velja AB ≠ BA.

Matrike so antikomutativne če velja AB = -BA.

Strassenovo množenje matrik

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

Časovno zahtevnost

Strassenov postopek ima časovno zahtevnost O(n^{\log_2 3}), 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.

Časovna zahtevnost 7 podproblemov

Časovna zahtevnost je po izreku O(n^{\log_2 7}) = O(n^{2.807}); enačba je T(n) = 7T(n / 2) + O(n2).

(Izboljšava: O(n2.378))

Primer

Konkreten primer.

Pa si od bližje poglejmo spodnjo tabelo. Opazimo, da je tabela razdeljena na sedem diagonal, sedem matrik.

Prva diagonala, ki je v tabeli označena z modro barvo, je iz samih ničel.

Druga diagonala je označena z rdečo barvo. Elemente diagonale dobimo tako, da zmnožimo dimenzije dveh zaporednih matrik.

Izračun elementov v drugi diagonali:

  • A0 * A1 = 5 * 6 * 6 = 180,
  • A1 * A2 = 6 * 6 * 2 = 72,
  • A2 * A3 = 6 * 2 * 5 = 60,
  • A3 * A4 = 2 * 5 * 8 = 80,
  • A4 * A5 = 5 * 8 * 5 = 200,
  • A5 * A6 = 8 * 5 * 5 = 200.


Tretja diagonala je v naši tabeli obarvana z zeleno barvo. Elemente izračunamo s pomočjo z zgornje karakteristične enačbe. Izračun elementov (podproblemov) tretje diagonale.

  • Prvi element.

Podproblem: A0 * A1 * A2.

     N0,2 = N0,0 + N1,2 * d0 * d1 * d3 = 0 + 72 + 5 * 6 * 2 = 132; k = 0
          = N0,1 + N2,2 + d0 * d2 * d3 = 180 + 0 + 5 * 6 * 2 = 240 
  • Drugi element.

Naslednji podproblem: A1 * A2 * A3.

   N1,3 = N1,1 + N2,3 * d1 * d2 * d4 = 0 + 60 + 6 * 6 * 5 = 210
        = N1,2 + N3,3 + d1 * d3 * d4 = 72 + 0 + 6 * 2 * 5 = 132 ; k = 2

Po enakem postopku izračunamo ostale elemente oziroma podprobleme, ki so:

  • A2 * A3 * A4 = 176; k = 2,
  • A3 * A4 * A5 = 160; k = 4,
  • A4 * A5 * A6 = 325; k = 5.


Naslednja diagonala je četrta diagonala, ki je obarvana z roza barvo. Tu računamo podprobleme:

  • A0 * A1 * A2 * A3 = 182; k = 2,
  • A1 * A2 * A3 * A4 = 248; k = 3,
  • A2 * A3 * A4 * A5 = 220; k = 2,
  • A3 * A4 * A5 * A6 = 210; k = 5.


Da ne bomo prikazovali samo, kako se izračunajo prvi elementi, si poglejmo, kako se izračunata zadnji element (podproblem) diagonale.

  • Zadnji podproblem: A3 * A4 * A5 * A6.
   N3,6 = N3,3 + N4,6 + d3 * d4 * d7 = 0 + 325 + 2 * 5 * 5 = 375
        = N3,4 + N5,6 + d3 * d5 * d7 = 80 + 200 + 2 * 8 * 5 = 360   
        = N3,5 + N6,6 + d3 * d6 * d7 = 160 + 0 + 2 * 5 * 5 = 210; k = 5


Ostale podprobleme računamo na enak način.

Podproblemi pete diagonale:

  • A0 * A1 * A2 * A3 * A4 = 292; k = 2,
  • A1 * A2 * A3 * A4 * A5 = 292; k = 2,
  • A2 * A3 * A4 * A5 * A6 = 300; k = 2.


Podproblema šeste diagonale:

  • A0 * A1 * A2 * A3 * A4 * A5 = 342; k = 2,
  • A1 * A2 * A3 * A4 * A5 * A6 = 342; k = 2.


Podproblem sedme diagonale:

  • A0 * A1 * A2 * A3 * A4 * A5 * A6 = 392; k = 2.

Izračun elementa sedme diagonale:

   N0,6 = N0,0 + N1,7 + d0 * d1 * d8 = 0 + 342 + 5 * 6 * 5 = 492
        = N0,1 + N2,6 + d0 * d2 * d8 = 180 + 300 + 5 * 6 * 5 = 630
        = N0,2 + N3,6 + d0 * d3 * d8 = 132 + 210 + 5 * 2 * 5 = 392; k = 2
        = N0,3 + N4,6 + d0 * d4 * d8 = 182 + 325 + 5 * 5 * 5 = 632 
        = N0,4 + N5,6 + d0 * d5 * d8 = 292 + 200 + 5 * 8 * 5 = 692
        = N0,5 + N6,6 + d0 * d5 * d8 = 342 + 0 + 5 * 5 * 5 = 467
        


Iz dimenzij diagonal dobimo d, s katerimi računamo:

  • A0 = 5 x 6 ---> d0 = 5 in d1 = 6
  • A1 = 6 x 6 ---> d2 = 6
  • A2 = 6 x 2 ---> d3 = 2
  • A3 = 2 x 5 ---> d4 = 5
  • A4 = 5 x 8 ---> d5 = 8
  • A5 = 8 x 5 ---> d6 = 5
  • A6 = 5 x 5 ---> d7 = 5


b) Tabela množenj:

A0 A1 A2 A3 A4 A5 A6
A0 0 180 132 {0} 182 {2} 292 {2} 342 {2} 393 {2}
A1 0 72 132 {2} 248 {2} 292 {2} 342 {2}
A2 0 60 176 {2} 220 {2} 300 {2}
A3 0 80 160 {4} 210 {5}
A4 0 200 325 {4}
A5 0 200
A6 0


c) Optimalni način množenja zgornjih matrik: Pri postavljanju oklepajev si pomagamo z zgoraj izračunanimi k-ji.

Koraki postavljanja oklepajev:

  • Pogledamo produkt: A0 * A1 * A2 * A3 * A4 * A5 * A6 . Zanima nas minimum, ki je pri k = 2. Zaklepaj postavimo za A2.
  • Pogledamo produkt: A0 * A1 * A2. Zanima nas minnimum, ki je pri k = 0. Zaklepaj postavimo za A0.
  • Nato pogledamo produkt A1 * A2. Zopet nas zanima minimum, ki je pri k = 1 in predklepaj postavimo pred A1
  • Naslednji produkt, ki nas zanima, je A3 * A4 * A5 * A6. Minimum je pri k = 5. Zaklepaj postavimo za A5.
  • Na koncu pogledamo še produkt: A3 * A4 * A5. Opazimo, da je minimum pri k = 4. Zaklepaj postavimoo za A4.


Optimalna rešitev: (A0 * (A1 * A2)) * ((A3 * A4) * A5) * A6)


Potrebujemo 392 množenj za množenje matrike 7 * 7 z zgoraj omenjenimi dimenzijami.
Osebna orodja