05 - Ritka mátrixok¶
Állítsuk elő a következő $N\times N$-es mátrixot sűrű (numpy), illetve ritka (scipy) mátrixként a két könyvtár kron függvénye segítségével $N=100,200,\dots,1000$ esetén! Készítsük el az $N$ hosszú $b$ vektort is!
$$M=\left(\begin{array}{rrrrrrr} 2 & -4 & 0 & 0 & \dots & 0 & 0\\ -4 & 2 & 0 & 0 & \dots & 0 & 0\\ 0 & 0 & 2 & -4 & \dots & 0 & 0\\ 0 & 0 & -4 & 2 & \dots & 0 & 0\\ \vdots & & & & \ddots & & \vdots\\ 0 & 0 & 0 & 0 & \dots & 2 & -4\\ 0 & 0 & 0 & 0 & \dots & -4 & 2\end{array}\right)\qquad b=\left(\begin{array}{c} 1\\ 2\\ 1\\ 2\\ \vdots\\ 1\\ 2 \end{array}\right)$$Minden méret esetén a ritka és a sűrű esetben is keressük meg azt az $u$ vektort, amelyre $M\cdot u = b$, mérjük meg a megoldás futási idejét, és ábrázoljuk azt két görbén a méret függvényében! Mit vehetünk észre?
A futási idő méréséhez keressünk rá a time modul time() függvényére!
Megoldás¶
Először, meghívjuk a szükséges csomagokat
from scipy import sparse as sp # A ritkamátrixokhoz
from scipy.sparse.linalg import spsolve # A ritkamátrixok egyenletének megoldásához
import numpy as np # A sűrűmátrixokhoz
from time import time # Az időméréshez
from matplotlib.pyplot import * # Az ábrázoláshoz
%matplotlib inline
Ezután a két csomag kron() függvényével elkészítjük a kezelendő objektumokat. Az azonos típusú mátrixokat, vektorokat tömbökben tároljuk, hogy egyszerűen kezelhessük őket.
Msc = list() # Lista a scipy mátrixainak
Mnp = list() # lista a numpy mátrixainak
bsc = list() # lista a scipy vektorainak
bnp = list() # lista a numpy vektorainak
for i in range(10): # legyártjuk az objektumokat, mindegyiket 10 mérteben
Msc += [sp.kron(sp.eye((i + 1) * 50), np.array([[2, -4], [-4, 2]]))]
Mnp += [np.kron(np.eye((i + 1) * 50), np.array([[2, -4], [-4, 2]]))]
bsc += [sp.kron(np.matrix(np.ones((i + 1) * 50)).T, np.array([[1], [2]]))]
bnp += [np.kron(np.matrix(np.ones((i + 1) * 50)).T, np.array([[1], [2]]))]
Majd megoldjuk az egyenleteket. A ritkamátrixokat a sparse.linalg.spsolve() metódussal, míg a sűrűmátrixokat a numpy.solve() metódussal. Az időt úgy mérjük, hogy a megoldás előtt és után megmérjük az időt a time() metódussal, és vesszük a különbségüket.
tsc = list() # lista a scipy megoldásai idejének
tnp = list() # lista a numpy megoldásai idejének
usc = list() # lista a scipy megoldásainak
unp = list() # lista a numpy megoldásainak
for i in range(10): # Megoldjuk mindkét csomag objektumai egyenleteit minden méret esetén, miközben az időt is mérjük
t = time()
usc += [sp.linalg.spsolve(Msc[i], bsc[i])]
tsc +=[time() - t]
t = time()
unp += [np.linalg.solve(Mnp[i], bnp[i])]
tnp +=[time() -t]
Végül ábrázoljuk a kapott eredményeket.
a = np.linspace(100, 1000, 10)
plot(a, tsc, "b-o", label="idok sparse-szal")
plot(a, tnp, "g-o", label="idok numpy-jal")
legend(loc=0)
title("Az egyenlet megoldásának ideje a mátrix méretének függvényében", size=20, y = 1.05)
xlabel("mátrix mérete", size=12)
ylabel("megoldás ideje (s)", size=12)
Látszik, hogy nagyobb mátrixok esetén rtkamátrixokkal dolgozni gyorsabb, de a részletekért ábrázoljuk őket külön logaritmikus skálán.
Először a ritkamátrixok megoldását.
loglog(a, tsc, "b-o")
xlabel("mátrix mérete")
ylabel("megoldás ideje(s)")
Majd a sűrűmátrixokét..
loglog(a, tnp, "g-o")
xlabel("mátrix mérete")
ylabel("megoldás ideje(s)")
Tehát a numpy csomag mátrixegyenletét megoldani a méret négyzetével arányos időbe kerül (ezt is várjuk, hiszen az elvégzendő műveletek is a méret négyzetével arányosak), míg ilyen egyszerű mátrix esetén ritkamátrixokkal dolgozva (kellően nagy méret esetén) még a lineárisnal is kisebb a méret és a megoldási idő közötti kapcsolat. Így ilyen esetekben valóban megéri a ritkamátrixokat használni.