GNU Octave/Macierz rzadka

Macierz rzadka

Najprostszym sposobem przechowania macierzy w pamięci komputera jest zapamiętanie jej rozmiarów i ciągu wszystkich elementów macierzy, wiersz po wierszu. Jeśli jednak macierz jest szczególnej postaci można optymalizować sposób przechowywania macierzy w pamięci komputera. Macierz rzadka to macierz, w której występuje dużo zer, wystarczy zatem pamiętać pola niezerowe, tj. zbiór trójek: (numer_wiersza, numer_kolumny, wartość), a pozostałe elementy macierzy są zerami (Uwaga. Faktyczna implementacja macierzy rzadkiej może być zupełnie inna). Dzięki macierzom rzadkim można oszczędzić pamięć, wykonać niektóre algorytmy szybciej, ale niektóre też wolniej, zwłaszcza jeśli wymagają konwersji na postać normalną.

Utworzyć macierz rzadką, przekształcić ją na normalną i spowrotem na rzadką, dla macierzy:

${\begin{pmatrix}0&13&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&11\\0&0&0&0&0\\-1&0&0&0&0\end{pmatrix}}$

Zadajemy macierz w formacie sparse: wektor współrzędnych x-owych, wektor współrzędnych y-owych, wektor wartości i rozmiary macierzy:

octave:6> x=[6,1,4];
octave:7> y=[1,2,5];
octave:8> v=[-1,13,11];
octave:9> A=sparse(x,y,v)
A =
  (6 , 1) -> -1
  (1 , 2) -> 13
  (4 , 5) -> 11

Konwersja do trybu normalnego full i z powrotem sparse:

octave:14> B=full(A)
B =
    0   13    0    0    0
    0    0    0    0    0
    0    0    0    0    0
    0    0    0    0   11
    0    0    0    0    0
   -1    0    0    0    0
octave:15> C=sparse(B)
C =
  (6 , 1) -> -1
  (1 , 2) -> 13
  (4 , 5) -> 11

Zauważmy, że zamist 36 liczb zmiennoprzecinowych składających się na macierz A wystarczy zapamiętać tylko 6 małych liczb całkowitych i 3 zmiennoprzecinokowe w formacie rzadkim.