A mátrixot általában kétdimenziós tömbként tárolják. A tömb minden egyes bejegyzése a mátrix egy-egy ai,j elemét jelenti, és a két indexszel i és j érhető el. Hagyományosan i a sorindex, felülről lefelé számozva, j pedig az oszlopindex, balról jobbra számozva. Egy m × n mátrix esetén a mátrix ilyen formátumú tárolásához szükséges memória mennyisége m × n arányos (figyelmen kívül hagyva, hogy a mátrix dimenzióit is tárolni kell).
Ritkás mátrix esetén jelentős memóriaigény-csökkenés érhető el, ha csak a nem nulla bejegyzéseket tároljuk. A nem nulla bejegyzések számától és eloszlásától függően különböző adatszerkezetek használhatók, amelyek az alapmegközelítéshez képest hatalmas memóriamegtakarítást eredményeznek. A kompromisszum az, hogy az egyes elemekhez való hozzáférés bonyolultabbá válik, és további struktúrákra van szükség ahhoz, hogy az eredeti mátrixot egyértelműen vissza lehessen állítani.
A formátumok két csoportra oszthatók:
- A hatékony módosítást támogató formátumok, mint például a DOK (Dictionary of keys), a LIL (List of lists) vagy a COO (Coordinate list). Ezeket általában a mátrixok felépítésére használják.
- Azok, amelyek támogatják a hatékony hozzáférést és a mátrixműveleteket, mint például a CSR (Compressed Sparse Row) vagy a CSC (Compressed Sparse Column).
Dictionary of keys (DOK)Edit
A DOK egy szótárból áll, amely (sor, oszlop)párokat képez le az elemek értékére. A szótárból hiányzó elemeket nullának vesszük. A formátum jó egy ritka mátrix véletlenszerű sorrendben történő inkrementális felépítésére, de rossz a nem nulla értékek lexikográfiai sorrendben történő iterálására. Az ember általában ebben a formátumban konstruál egy mátrixot, majd a feldolgozáshoz egy másik, hatékonyabb formátumba konvertálja.
List of lists (LIL)Edit
A LIL soronként egy listát tárol, ahol minden bejegyzés tartalmazza az oszlopindexet és az értéket. Általában ezeket a bejegyzéseket oszlopindex szerint rendezve tartjuk a gyorsabb keresés érdekében. Ez egy másik formátum, amely jól használható inkrementális mátrixépítéshez.
Koordinátalisták (COO)Edit
COO egy (sor, oszlop, érték) tuplikból álló listát tárol. Ideális esetben a bejegyzések először sorindex, majd oszlopindex szerint vannak rendezve, a véletlenszerű hozzáférési idők javítása érdekében. Ez egy másik formátum, amely jól használható inkrementális mátrixépítéshez.
Tömörített ritka sor (CSR, CRS vagy Yale formátum)Edit
A tömörített ritka sor (CSR) vagy tömörített sortárolás (CRS) vagy Yale formátum egy M mátrixot három (egydimenziós) tömb által reprezentál, amelyek a nem nulla értékeket, a sorok kiterjedését, illetve az oszlopindexeket tartalmazzák. Hasonló a COO-hoz, de a sorindexeket tömöríti, innen a neve. Ez a formátum gyors sorelérést és mátrix-vektor szorzásokat (Mx) tesz lehetővé. A CSR formátumot legalább az 1960-as évek közepe óta használják, az első teljes leírás 1967-ben jelent meg.
A CSR formátum három (egydimenziós) tömb (V, COL_INDEX, ROW_INDEX) segítségével tárolja az M gyér m × n mátrixot soros formában. Jelölje NNZ az M-ben lévő nem nulla bejegyzések számát. (Megjegyezzük, hogy itt nulla alapú indexeket kell használni.)
- A V és COL_INDEX tömbök NNZ hosszúságúak, és tartalmazzák a nem nulla értékeket, illetve ezen értékek oszlopindexeit.
- A ROW_INDEX tömb hossza m + 1, és azt az indexet kódolja V-ben és COL_INDEX-ben, ahol az adott sor kezdődik. Az utolsó elem az NNZ , azaz, a fiktív index a V-ben közvetlenül az utolsó érvényes NNZ – 1 index után.
Például a mátrix
( 5 0 0 0 0 0 8 0 0 0 0 0 3 0 0 0 6 0 0 0 ) {\displaystyle {\begin{pmatrix}5&0&0&0&0&0\\0&8&0&0&0\\\0&0&3&0\\\0&6&0&0&0\\\\\\end{pmatrix}}}
egy 4 × 4 mátrix 4 nem nulla elemmel, tehát
V = COL_INDEX = ROW_INDEX =
feltételezve egy nullás indexű nyelvet.
Egy sor kivonásához először definiáljuk:
row_start = ROW_INDEX row_end = ROW_INDEX
Majd szeleteket veszünk V-ből és COL_INDEX-ből a row_start-tól kezdve a row_end-ig.
Ezért a mátrix 1. sorának (a második sornak) a kivonásához megadjuk row_start=1 és row_end=2. Ezután elkészítjük a V = és COL_INDEX = szeleteket. Most már tudjuk, hogy az 1. sorban az 1. oszlopban van egy elemünk, amelynek értéke 8.
Ez esetben a CSR-reprezentáció 13 bejegyzést tartalmaz, szemben az eredeti mátrix 16 bejegyzésével. A CSR formátum csak akkor takarít meg memóriát, ha NNZ < (m (n – 1) – 1) / 2.Egy másik példa, a mátrix
( 10 20 0 0 0 0 0 0 30 0 40 0 0 0 0 0 50 60 70 0 0 0 0 0 0 0 0 0 80 ) {\displaystyle {\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}}
egy 4 × 6 mátrix (24 bejegyzés) 8 nem nulla elemmel, így
V = COL_INDEX = ROW_INDEX =
az egészet 21 bejegyzésként tároljuk.
- ROW_INDEX a V tömböt sorokra osztja:
(10, 20) (30, 40) (50, 60, 70) (80); - COL_INDEX az értékeket oszlopokba rendezi:
(10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).
Megjegyezzük, hogy ebben a formátumban a ROW_INDEX első értéke mindig nulla, az utolsó pedig mindig NNZ, így bizonyos értelemben redundánsak (bár azokon a programozási nyelveken, ahol a tömb hosszát explicit módon kell tárolni, az NNZ nem lenne redundáns). Mindazonáltal így nem kell kivételes esetet kezelni az egyes sorok hosszának kiszámításakor, mivel garantálja, hogy a ROW_INDEX – ROW_INDEX képlet bármely i sorra működik. Ráadásul ennek a redundáns tárolásnak a memóriaköltsége egy kellően nagy mátrix esetében valószínűleg jelentéktelen.
A (régi és új) Yale sparse mátrixformátumok a CSR séma példányai. A régi Yale formátum pontosan a fent leírtak szerint működik, három tömbtel; az új formátum a ROW_INDEX és COL_INDEX tömböket egyetlen tömbben egyesíti, és a mátrix átlóját külön kezeli.
A logikai szomszédsági mátrixok esetében az adattömb elhagyható, mivel a bináris szomszédsági kapcsolat modellezéséhez elegendő egy bejegyzés létezése a sortömbben.
Valószínűleg Yale-formátumként ismert, mert a Yale Sparse Matrix Package 1977-es jelentésében javasolták a Yale Egyetem Számítástechnikai Tanszékének (Department of Computer Science).
Tömörített ritka oszlop (CSC vagy CCS)Edit
A CSR-hez hasonló, kivéve, hogy az értékeket először oszloponként olvassa be, minden értékhez sorindexet tárol, és oszlopmutatókat tárol. A CSC például (val, row_ind, col_ptr), ahol val a mátrix (fentről lefelé, majd balról jobbra) nem nulla értékeit tartalmazó tömb; row_ind az értékeknek megfelelő sorindexek; és col_ptr a val indexek listája, ahol minden oszlop kezdődik. A név azon alapul, hogy az oszlopindex-információ a COO formátumhoz képest tömörített. A felépítéshez jellemzően más formátumot (LIL, DOK, COO) használunk. Ez a formátum hatékony az aritmetikai műveletekhez, oszlopszeleteléshez és mátrix-vektor szorzathoz. Lásd scipy.sparse.csc_matrix.Ez a hagyományos formátum egy ritka mátrix megadására a MATLAB-ban (a sparse függvényen keresztül).