Množenje pravokotnih matrik

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina


Izračuanti želimo produkt n matrik M1,M2,...,Mn − 1,Mn različnih dimenzij. Ker je množenje matrik asociativno lahko poljubno postavimo oklepaje, vrstnega reda matrik pa ne smemo menjati. Število osnovnih aritmetičnih operacij, ki jih opravimo, je odvisno od razporeditve oklepajev. Postavi se vprašanje, kako množiti, da bo število operacij čim manjše.

Zgled

Za množenje pravokotnih matrik A in B, kjer je A dimenzije p \times r in B dimenzije r \times s, potrebujemo p \cdot r \cdot s množenj (zanimajo nas samo množenja, ker so bolj zahtevna od seštevanj). Če množimo tri matrike A (dimenzije p \times r), B (dimenzije r \times s) in C (dimenzije s \times t), lahko to storimo na dva načina:

  1. (A_{pr} \cdot B_{rs}) \cdot C_{st}= D_{ps} \cdot C_{st} Število operacij: p \cdot r \cdot s + p \cdot s \cdot t
  2. A_{pr} \cdot (B_{rs} \cdot C_{st})=A_{pr} \cdot E_{rt} Število operacij: r \cdot s \cdot t + p \cdot r \cdot t

Vidimo, da je optimalen način množenja odvisen od dimenzij matrik, na primer, če je r velik, je bolje množiti na prvi način.

Algoritem

Uporabimo dinamično programiranje.

Zaporedje odločitev

Rešitev problema zapišemo kot zaporedje odločitev: Na vsakem koraku se odločimo, kako bomo postavili oklepaje.

Najprej se odločimo kako bomo začetni izraz z oklepaji razdelili na dva dela: (M_1 \cdot M_2 \cdot ... \cdot M_{k-1} \cdot M_k) \cdot (M_{k+1} \cdot M_{k+2} \cdot... \cdot M_{n-1} \cdot M_n)
Potem pa se odločamo, kako bomo delili vsakega od delov. Postopek ponavljamo, dokler nimamo postavljenih oklepajev že okoli vsake matrike.

Pravilo optimalnosti

Preverimo pravilo optimalnosti (to je, vsako podzaporedje zaporedja odločitev, ki generira optimalno rešitev, mora biti optimalno). Pa denimo, da v optimalni postavitvi oklepajev obstajajo matrike Mi,Mi + 1,...,Mj − 1,Mj obdane z oklepajem, za katerega velja, da znotraj njega nadaljnji oklepaji niso postavljeni optimalno. Torej postavitev oklepajev na tem delu lahko popravimo do optimalnega, saj je končno število operacij vsota števil operacij potrebnih za množenje v vseh notranjih oklepajih (torej tudi v temu neoptimalnemu). Torej se tudi končna rešitev izboljša. Protislovje s predpostavko, da je končna rešitev optimalna.

Rekurzivne enačbe

S pomočjo pravila optimalnosti zapišemo rekurzivne enačbe. Naj bo mij najmanjše število operacij potrebnih za množenje matrik Mi,Mi + 1,...,Mj − 1,Mj. Denimo, da oklepaje postavimo takole:

(M_i \cdot M_{i+1} \cdot ... \cdot M_{k-1} \cdot M_k) \cdot (M_{k+1} \cdot M_{k+2} \cdot... \cdot M_{j-1} \cdot M_j)

in naj bo zmnožek levega oklepaja matrika dimenzij p \times r ter zmnožek levega oklepaja matrika dimenzij r \times s.

m_{ij}=\min_{i \leq k<j} \{ prs+m_{ik}+m_{(k+1)j} \}, kjer je mii = 0 za vse i.

Število prs je število operacj potrebnih za množenje na zadnjem koraku med levim in desnim oklepajem, mik število operacij potrebnih za množenje levega oklepaja in m(k + 1)j število operacij potrebnih za množenje desnega oklepaja.

Rešujemo od spodaj navzgor (najprej izračunamo mii, nato mi(i + 1), mi(i + 3) in tako dalje).

Iščemo m1n.

Primer

M_{10,20} \cdot M_{20,50} \cdot M_{50,1} \cdot M_{1,100}

m_{11}=m_{22}=m_{33}=m_{44}= \, 0
m_{12}=min \{ 10 \cdot 20 \cdot 50 + m_{11} \}=10000
m_{23}=min \{ 20 \cdot 50 \cdot 1 + m_{22} \}=1000
m_{34}=min \{ 50 \cdot 1 \cdot 100 + m_{33} \}=5000
m_{13}=min \{ 10 \cdot 20 \cdot 1 + m_{11} + m_{23}, 10 \cdot 50 \cdot 1 + m_{12} + m_{33} \}=1200
m_{24}=min \{ 20 \cdot 50 \cdot 100 + m_{22} + m_{34}, 20 \cdot 1 \cdot 100 + m_{23} + m_{44} \}=3000
m_{14}=min \{ 10 \cdot 20 \cdot 100 + m_{11} + m_{24}, 10 \cdot 50 \cdot 100 + m_{12} + m_{34}, 10 \cdot 1 \cdot 100 + m_{13} + m_{44} \}=2200

Torej je najmanjše število operacij potrebnih za množenje matrik 2200.

Pogledamo še, kako moramo matrike asociirati, da dobimo ta optimum:

  • Minimum m14 smo dobili iz tretje možnosti (k = 3). Torej moramo matrike zmnožiti takole:

(M_{10,20} \cdot M_{20,50} \cdot M_{50,1}) \cdot (M_{1,100})

  • Minimum m13 smo dobili iz prve možnosti (k = 1). Torej moramo matrike zmnožiti takole:

((M_{10,20}) \cdot (M_{20,50} \cdot M_{50,1})) \cdot (M_{1,100})

Opomba:

Najslabši vrstni red množenja je M_{10,20} \cdot (M_{20,50} \cdot (M_{50,1} \cdot (M_{1,100})), pri katerem potrebujemo 125000 operacij. Vidimo, da se res izplača paziti na vrstni red množenja.

Osebna orodja