Računalništvo

Strassenovo množenje

Na predavanjih smo naredili Strassenovo množenje matrik, ki deluje v času $O(n^{\log_2 7})$. To je bolje od naivnega množenja, ki deluje v času $O(n^3)$, vendar smo opazili, da Strassenovo množenje zahteva več seštevanj. Na teh vajah bomo ugotavljali, kako velike morajo biti matrike, da se splača uporabiti Strassenovo množenje.

Strassenovo množenje iz predavanj bomo najprej izboljšali. Omejimo se na množenje kvadratnih matrik $A$ in $B$ velikosti $n \times n$.

Na predavanjih smo po potrebi na začetku postopka povečali $n$ do potence števila $2$ in dopolnili $A$ in $B$ z ničlami. To je preveč potratno, zato raje delamo takole:

• če je $n$ sodo število, uporabimo $A$ in $B$
• če je $n$ liho število, $A$ in $B$ dodamo en stolpec in vrstico ničel

Poleg tega bomo bolj pazljivo delali s tabelami, da ne bi po nepotrebnem tratili pomnilnika.

Izboljšana implementacija je na voljo v datoteki strassen.py.

Naloga 1

V celoti preglejte kodo v datoteki strassen.py, da boste razumeli, kaj dela. Osredotočite se na funkcijo strassen(a, b, minsize=1). Ali razumete, kaj dela parameter minsize? Strassenovo množenje deluje s strategijo deli in vladaj, torej rekurzivno deli matrike na manjše. Funkcija strassen matrik manjših od minsize ne deli več, ampak jih neposredno množi z naivnim algoritmom.

Naloga 2

Potrebujemo še kodo, ki izmeri, koliko časa potrebuje klic dane funkcije:

import time

def stopaj(f,*x,**kw):
    """stopaj(f, args) vrne časa izvajanje klica funkcije f(args) v sekundah."""
    zacetek = time.process_time()
    f(*x,**kw)
    konec = time.process_time()
    return (konec - zacetek)

Sestavite funkcijo meritev(n, minsize), ki izmeri koliko časa potrebujemo za množenje dveh matrik velikosti $n \times n$ z naivnim množenjem produkt in koliko s Strassenovim množenjem strassen pri dani vrednosti minsize. Funkcija naj vrne razliko v času.

Namiga:

• nalogo rešuje v ločeni datoteki eksperiment.py in ne packajte po strassen.py; v eksperiment.py lahko uvozite strassen.py z ukazom from strassen import *.
• na voljo je funkcija nakljucna(n) ki ustvari naključno matriko velkosti $n \times n$. (Ste prebrali strassen.py v celoti?)

Naloga 3

Odkrijte velikost matrike n in vrednost parametra minsize, pri katerih je strassen hitrejši od produkt.

Naloga 4

Kako bi ugotovili optimalno vrednost parametra minsize v funkciji strassen? Naredite eksperimente, s pomočjo katerih lahko ocenite optimalno vrednost minsize.

Naloga 5

Narišite graf, ki prikazuje izmerjeno časovno zahtevnost funkcij produkt in strassen (z optimalno vrednostjo minsize, ki ste jo našli v prejšnji nalogi). S katerim orodjem boste narisali graf? (Če z Mathematico, uporabite ListPlot).

Ocenite, ali je časovna zahtevnost produkt res $O(n^3)$ in časovna zahtevnost strassen res $O(n^{\log_2 7})$. V Mathematici lahko v ta namen uporabite funkcijo Fit.