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³ da bi pomnožio dve n × 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 × m matricu A i m × p matrica B, onda je C n × 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 × n, u kom slučaju je vreme izvršenja Θ(n³).

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 > 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³) 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 √M √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ⁿ × 2ⁿ 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₁₁ = a₁₁b₁₁ 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²) da bi se sabrala 4 para rezultujućih matrica. Primena ove teoreme pokazuje da rekurzija ima rešenje Θ(n³) 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 × m za A i m × 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š

• Kuk-Janger-Kasami algoritam
• Množenje lanaca matrica

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

• "Cache oblivious algorithms" by Harald Prokop
• Toward an optimal algorithm for matrix multiplication
• Numerical Recipes: The Art of Scientific Computing