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 n3 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:

.

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 Θ(n3).

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 Θ(n3) 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:

.

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

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 c11 = a11b11 kao bazni slučaj. Kompleksnost ovog algoritma u funkciji od n je dat rekurzijom:

;
,

računajuci 8 rekurzivnih poziva matrice velicine n/2 i Θ(n2) da bi se sabrala 4 para rezultujućih matrica. Primena ove teoreme pokazuje da rekurzija ima rešenje Θ(n3) 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:
  • Else, if max(n, m, p) = p, podeliti B vertikalno:
  • Else, max(n, m, p) = m. Podeliti A vertikalno i B horizontalno:

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

Drugi algoritmi za množenje matrica[уреди]

  • Podkubni algoritam
  • Paralelni i distribuirani algoritmi

Vidi još[уреди]

Reference[уреди]

Spoljašnje veze[уреди]

  1. "Cache oblivious algorithms" by Harald Prokop
  2. Toward an optimal algorithm for matrix multiplication
  3. Numerical Recipes: The Art of Scientific Computing
  4. "Sorting and searching" by Steven S. Skiena