Algoritam množenja matrica

Algoritam množenja matrica је opis rešavanja matematičkih operacija kod množenja matrica.

S obzirom da je množenje matrica centralna operacija u mnogim numeričkim algoritmima, mnogo truda je uloženo u izradu efikasnog algoritma množenja matrica. Primena množenja matrica u računskim problemima može se videti u mnogim poljima među kojima su i naučno računanje i prepoznavanje obrazaca, kao i u naizgled nepovezanim problemima poput računanja putanja u grafu. Mnogi različiti algoritmi su pravljeni za množenje matrica na različitim tipovima hardvera, uključujući paralelne i distribuirane sisteme, gde se proces računskog posla odvija prošireno na više procesora, npr. preko mreže.

Direktna primena matematičke definicije množenja matrica daje nam algoritam kome je potrebno vremena reda $n 3$ da bi pomnožio dve $n \times n$ matrice. Bolje asimptotske granice vremena potrebnog za množenje matrica poznata su još od rada Štrasena u 1960-im godinama, ali još uvek nije poznato optimalno vreme, tj. kompleksnost problema.

Problem najbržeg algoritma za množenje matrica predstavlja jedan od nerešenih problema u računarskim naukama.

Iterativni algoritam

Definicija množenja matrica je: ako je $C = AB$ za $n \times m$ matricu A i $m \times p$ matrica B, onda je C $n \times p$ matrica sa unosom:

c_{ij}=\sum _{k=1}^{m}a_{ik}b_{kj}

.

Iz ovoga, jednostavan algoritam može biti konstruisan koji se ponavlja u petlji preko indeksa i od 1 do n i j od 1 do p, računajući jednačinu iznad koristeći ugnježdenu petlju:

   Input: matrices A and B
   Let C be a new matrix of the appropriate size
   For i from 1 to n:
       For j from 1 to p:
           Let sum = 0
           For k from 1 to m:
               Set sum ← sum + Aik × Bkj
           Set Cij ← sum
   Return C

Ovaj algoritam se izvršava u $Θ(nmp)$ vremenu u asimptotskoj notaciji. Uobičajeno pojednostavljenje u cilju analize algoritama jeste pretpostavka da su ulazi sve kvadratne matrice dimenzija $n \times n$ , u kom slučaju je vreme izvršenja $Θ(n 3)$ .

Keš ponašanje

Tri petlje u iterativnom množenju matrica mogu se proizvoljno zameniti bez uticaja na tačnost ili asimptotsko vreme izvršenja algoritma. Međutim, red može imati značajan uticaj na praktičnu performansu zbog obrazaca pristupa memoriji i keš korišćenja algoritma. Koji redosled je najbolji takođe zavisi od toga da li se matrice čuvaju u redosledu prvo red, redosledu prvo kolona, ili mešavina oba.

Konkretno, u idealnom slučaju potpuno asocijativog keša koji se sastoji od M keš linija po b bajtova svaki, gorepomenuti algoritam je podoptimalan za A i B koji se čuvaju u redosledu prvo red. Kada je $n > .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/M'b$ , svaka iteracija unutrašnje petlje vodi do promašaja keša kada se pristupa redu B. To znači da algoritam snosi $Θ(n 3)$ keš promašaja u najgorem slučaju. Od 2010. godine, memorijske brzine upoređene sa brzinama procesora su takve da keš promašaji, a ne stvarni proračuni, dominiraju vremenom izvršenja za prilično velike matrice.

Optimalna varijanta iterativnog algoritma za A i B u rasporedu prvo red je verzija sa pločicama, gde je matrica implicitno podeljena na kvadratne pločice veličine $\sqrt M$ $\sqrt M$

   Input: matrices A and B
   Let C be a new matrix of the appropriate size
   Pick a tile size T = Θ(√M)
   For I from 1 to n in steps of T:
       For J from 1 to p in steps of T:
           For K from 1 to m in steps of T:
               Multiply AI:I+T, K:K+T and BK:K+T, J:J+T into CI:I+T, J:J+T, that is:
               For i from I to min(I + T, n):
                   For j from J to min(J + T, p):
                       Let sum = 0
                       For k from K to min(K + T, m):
                           Set sum ← sum + Aik × Bkj
                       Set Cij ← sum
   Return C

U idealizovanom keš modelu, ovaj algoritam snosi samo Θ(n3/b √M) keš promašaja, delilac b √M iznosi nekoliko redova veličine na modernim mašinama, tako da stvarni proračuni dominiraju vremenom izvršenja, a ne keš promašaji.

Zavadi pa vladaj algoritam

Alternativa iterativnom algoritmu je "Zavadi pa vladaj" algoritam za množenje matrica. Ovo se odnosi na podelu blokova:

C={\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}},\,A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}},\,B={\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}}

.

što radi za sve kvadratne matrice čije su dimenzije stepeni broja 2, npr. oblici su $2 n \times 2 n$ za neko n. Proizvod matrica je sad:

{\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}}{\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}

koji se sastoji od 8 množenja parova podmatrica, praćeno korakom sabiranja. Zavadi pa vladaj algoritam računa najmanja množenja rekurzivno, koristeći skalarno množenje $c 11 = a 11 b 11$ kao bazni slučaj. Kompleksnost ovog algoritma u funkciji od n je dat rekurzijom:

T(1)=\Theta (1)

;

T(n)=8T(n/2)+\Theta (n^{2})

,

računajuci 8 rekurzivnih poziva matrice velicine $n /2$ i $Θ(n 2)$ da bi se sabrala 4 para rezultujućih matrica. Primena ove teoreme pokazuje da rekurzija ima rešenje $Θ(n 3)$ kao i iterativni algoritam.

Nekvadratne matrice

Varijanta ovog algoritma koja radi za matrice proizvoljnih dimenzija i brža je u praksi deli matrice na dve umesto na četiri podmatrice, kao što je prikazano ispod. Neka su dimenzije matrica $n \times m$ za A i $m \times p$ za B. Deljenje matrice znači deliti je na dva dela jednakih veličina, ili što je bliže moguće u slučaju matrica neparnih dimenzija.

Bazni slučaj: ako je $max(n, m, p)$ ispod određene granice, koristiti verziju odmotavanja petlji iterativnog algoritma.
Rekurzivni slučaj:

If $max(n, m, p) = n$ , podeliti A horizontalno:

C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{B}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}}

Else, if $max(n, m, p) = p$ , podeliti B vertikalno:

C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}}={\begin{pmatrix}AB_{1}&AB_{2}\end{pmatrix}}

Else, $max(n, m, p) = m$ . Podeliti A vertikalno i B horizontalno:

C={\begin{pmatrix}A_{1}&A_{2}\end{pmatrix}}{\begin{pmatrix}B_{1}\\B_{2}\end{pmatrix}}=A_{1}B_{1}+A_{2}B_{2}

Keš ponašanje

Stepen promašaja keša u rekurzivnom množenju matrica je isti kao i u iterativnoj verziji sa pločicama, ali za razliku od iterativnog algoritma, rekurzivni je nesvestan keša, što znači da nema podešavanja parametara potrebnih da bi se dobila optimalna performansa keša, i ponaša se dobro u multiprogramskim okruženjima, gde su keš veličine efikasno dnamične zbog drugih procesa koji zauzimaju keš prostor. Jednostavni iterativni algoritam je takođe nesvestan keša ali mnogo sporiji u praksi ako raspored matrica nije prolagođen algoritmu.

Broj keš promašaja u ovom algoritmu na mašini sa M linija idealnog keša, svaki veličine b bajtova je

\Theta \left(m+n+p+{\frac {mn+np+mp}{b}}+{\frac {mnp}{b{\sqrt {M}}}}\right)

Drugi algoritmi za množenje matrica

Podkubni algoritam
Paralelni i distribuirani algoritmi

Vidi još

Reference

Dodatna literatura

Skiena, Steven S. (2012). „Sorting and Searching”. The Algorithm Design Manual. стр. 103—144. ISBN 978-1-84800-069-8. doi:10.1007/978-1-84800-070-4_4.

Spoljašnje veze