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 Шаблон:Math da bi pomnožio dve Шаблон:Math 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 Шаблон:Math za Шаблон:Math matricu A i Шаблон:Math matrica B, onda je C Шаблон:Math 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 Шаблон:Math vremenu u asimptotskoj notaciji. Uobičajeno pojednostavljenje u cilju analize algoritama jeste pretpostavka da su ulazi sve kvadratne matrice dimenzija Шаблон:Math, u kom slučaju je vreme izvršenja Шаблон:Math.

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 Шаблон:Math, svaka iteracija unutrašnje petlje vodi do promašaja keša kada se pristupa redu B. To znači da algoritam snosi Шаблон:Math 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 Шаблон:Math Шаблон:Math

   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=\left(\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right),A=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right),B=\left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right)$.

što radi za sve kvadratne matrice čije su dimenzije stepeni broja 2, npr. oblici su Шаблон:Math za neko n. Proizvod matrica je sad:

$\left(\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right)=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right)\left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right)=\left(\begin{array}{cc}{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{array}\right)$

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 Шаблон:Math kao bazni slučaj. Kompleksnost ovog algoritma u funkciji od n je dat rekurzijom:

$T(1)=\mathrm{\Theta }(1)$;

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

računajuci 8 rekurzivnih poziva matrice velicine Шаблон:Math i Шаблон:Math da bi se sabrala 4 para rezultujućih matrica. Primena ove teoreme pokazuje da rekurzija ima rešenje Шаблон:Math 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 Шаблон:Math za A i Шаблон:Math 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 Шаблон:Math ispod određene granice, koristiti verziju odmotavanja petlji iterativnog algoritma.
• Rekurzivni slučaj:

• If Шаблон:Math, podeliti A horizontalno:

$C=\left(\begin{array}{c}{A}_1\\ A_2\end{array}\right)B=\left(\begin{array}{c}{A}_{1}B\\ A_{2}B\end{array}\right)$

• Else, if Шаблон:Math, podeliti B vertikalno:

$C=A\left(\begin{array}{cc}{B}_1& B_2\end{array}\right)=\left(\begin{array}{cc}A{B}_1& A{B}_2\end{array}\right)$

• Else, Шаблон:Math. Podeliti A vertikalno i B horizontalno:

$C=\left(\begin{array}{cc}{A}_1& A_2\end{array}\right)\left(\begin{array}{c}{B}_1\\ B_2\end{array}\right)=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

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

Drugi algoritmi za množenje matrica

• Podkubni algoritam
• Paralelni i distribuirani algoritmi

Vidi još

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

Dodatna literatura

• Шаблон:Cite book

Spoljašnje veze

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