markdown.md

Analiza časovne zahtevnosti

Za lažjo analizo bomo predpostavili naslednje:

• Kot prej poimenujmo levo matriko ki jo množimo: A, desno: B, trenutno (self): C in po potrebi delovno D
• Naj za te matrike velja: A je N × M matrika, B je M × K matrika, iz tega torej sledi da sta C in D N × K matriki
• Nadalje naj velja n := N // 2, m := M // 2, k := K // 2 in L = max{N, M, K} ter l = L // 2 = max{n, m, k}
• Seštevanje in množenje skalarjev ima konstantno časovno in prostorsko zahtevnost
• Dostop do posamezne matrike/podmatrike ima konstantno časovno zahtevnosz (če ne pride do kopiranja), v nasprotnem primeru je njegova časovna zahtevnost O(NK), če dostopamo do matrike N × M
• Prepisovanje posamezne matrike/podmatrike velikosti N × M ima časovno zahtevnost O(NM) in porabi O(1) dodatnega prostora.
• Seštevanje/odštevanje dveh N × M matrik ima časovno zahtevnost O(NM), ter ob ustvarjanju nove matrike porabi O(NM) dodatnega spomina
• Prištevanje/odštevanje (z operatorjema += in -=) dveh N × M matrik, ki se v nadmatriki ne prekrivata ima časovno zahtevnost O(NM), ter porabi O(1) dodatnega spomina (po popravku, matrik, ki se prekrivaju ne bomo prištevali in se zato z njihovo prostorsko zahtevnostjo ne bomo ukvarjali)
• Pomnoževanje matrike s skalarjem (A *= k, za skalarni k), kjer je A N × M matrika ima časovno zahtevnost O(NM) in porabi O(1) dodatnega prostora.

Analiza

1. Naivno množenje

   Metoda dot_product sešteje a produktov (opravi 2*a osnovnih operacij), torej je njena časovna zahtevnost O(a), ker jo uporabljamo za skalarnih produt dveh vektorjev je to kar enako dolžini enega izmed njih, v primeru naše matrike pa kar številu stolpcev v A in številu vrstic v B torej O(M).

   Metoda multiply vsebuje dve gnezdeni for zanki, ki se izvedeta do konca, zunanja se izvede N-krat, notranja K krat, v notranji pa dot_product na vektorju dolžine M. Torej je časovna zahtevnost metode multiply v razredu SlowMatrix O(NMK).

2. Strassenovo množenje

   Najprej se osredotočimo na primer, ko so vse dimenzije tako A in B matrike deljive z 2, v baznem primeru v najslabšem primeru opravimo N × M × K operacij, kjer je vsaj ena izmed konstant enaka 1, kar nas v tem primeru še vedno pusti v časovni zahtevnosti O(L^2).

   Za analizo časovne zahtevnosti bomo uporabili krovni izrek (Master Theorem), kjer se bomo pri končni analizi, zaradi omejitev le-tega na zgolj eno spremenljivko v rekurzivni zvezi, omejili na največjo izmed dimenzij matrik (L).

   Priprava primernih podmatrik zahteva konstantno časovno zahtevnost, nato sledi 8 seštevanj matrik (4 × n × m in 4 × m × k), kar lahko skupno omejimo z O(l²) = O(L²).

   Sledi 7 rekurzivnih množenj na matrikah pol manjših velikosti (n × m × m × k matrike), kar lahko na podlagi krovnega izreka zapišemo kot 7T(L/2). Potem pa je potrebno dobljene produkte še sestaviti nazaj v skupno matriko, kar vsebuje 7 seštevanj n × k matrik in kriiranje treh novih n × k matrik, kar lahko spet omejimo z O(l^2) = O(L^2)

   Ob prespostavki, da imamo matrike sodih dimenzij tako velja oblika krovnega izreka: T(L) = 7×T(L/2) + O(L^2)

3. Strassenovo množenje z manjšo porabo spomina

   V razredu CheapMatrix je implementirana varainta Strassenovega algoritma, ki porabi manj spomina (dodatnega spomina porabi zgolj dovolj za vzdrževanje sklada ob rekurziji).

   Postopamo podobno kot pri standardni implementaciji Strassenovega algoritma, la da moramo biti pri vseh operacija pazljivi in namesto ustvarjanja novih matrik uporabljati spomin, ki nam je na voljo (leva(A) in desna(B) matrika, ki ju moramo po končanem opravljanju vrniti nazaj na prvotno stanje, matrika rezultata(C), ki mora na koncu vsebovati rezultat in delovna matrika(D), ki je enakih dimenzij kot C, o njej pa nimamo nobenih pogojev) in zato vse operacije izvajamo na mestu.

   Tako za računanje produktov vsto bločnih matrik, kjer smo lahko pri FastMatrix uporabljali normalno seštevanje najprej popravimo osnovno matriko, opravimo množenje rekurzivno, kjer mu za delovno matriko podamo primerno bločno matriko v D nato pa prvotno matriko popravimo nazaj (odštejemo/prištejemo kar smo prej prišteli/odšteli). V svoji implementaciji sem za delovno matriko v rekurziji vseskozi uporabljal D22 saj sem tako imel proste roke za shranjevanje ostalih vmesnih matrik na ostala mesta v delovni matriki.

   Ko smo izračunali vseh 7 rekurzivnih množenj, ki si jih sranjujemo tako v C kot v D je potrebno vse te bločne matrike še zgolj sestaviti v C na pravilen način.

   Zadnji del je spet podoben delu v FastMatrix, la da je potrebno zopet paziti da na ustvarjamo novih matrik. Tako zopet sledimo isti ideji kot prej, na željeni matriki množimo levo in desno in to matriko. Za razliko od prej si je potrebno nekajkrat pred množenjem pospraviti ciljno matriko, čemur bi se sicer lahko izognili, če bi ob vsakem doprištevanju prepisali pravi del ciljne matrike, a se mi zdi da je zaradi jasnosti, za katero bločno matriko rezultata gre vredno žrtvovati nekaj dodatnih operacij.

   Ob obravnavanju robnih primerv zaradi lažjega zapisa/razumevanja do dvakrat usvarimo novo 1 × 1 matriko, da lahko normalno kličemo množenje.

   Zgolj zaradi preprostosti večino algoritma implementiramo v privatni metodi _multiply, kjer lahko eksplicitno zahtevamo podajanje delovne matrike.