Matice se obvykle ukládá jako dvourozměrné pole. Každý záznam v poli představuje prvek ai,j matice a přistupuje se k němu pomocí dvou indexů i a j. Obvykle i je řádkový index, číslovaný shora dolů, a j je sloupcový index, číslovaný zleva doprava. Pro matici m × n je množství paměti potřebné k uložení matice v tomto formátu úměrné m × n (bez ohledu na to, že je třeba uložit také rozměry matice).
V případě řídké matice lze podstatně snížit paměťové nároky uložením pouze nenulových položek. V závislosti na počtu a rozložení nenulových položek lze použít různé datové struktury, které ve srovnání se základním přístupem přinášejí obrovské úspory paměti. Kompromisem je, že přístup k jednotlivým prvkům se stává složitějším a jsou zapotřebí další struktury, aby bylo možné jednoznačně obnovit původní matici.
Formáty lze rozdělit do dvou skupin:
- Ty, které podporují efektivní modifikaci, například DOK (slovník klíčů), LIL (seznam seznamů) nebo COO (seznam souřadnic). Ty se obvykle používají ke konstrukci matic.
- Ty, které podporují efektivní přístup a operace s maticemi, například CSR (Compressed Sparse Row) nebo CSC (Compressed Sparse Column).
Slovník klíčů (DOK)Upravit
DOK se skládá ze slovníku, který mapuje (řádek, sloupec)-páry na hodnoty prvků. Prvky, které ve slovníku chybí, se považují za nulové. Tento formát je dobrý pro inkrementální konstrukci řídké matice v náhodném pořadí, ale špatný pro iteraci nad nenulovými hodnotami v lexikografickém pořadí. Člověk obvykle zkonstruuje matici v tomto formátu a pak ji pro zpracování převede do jiného efektivnějšího formátu.
Seznam seznamů (LIL)Upravit
LIL ukládá jeden seznam na řádek, přičemž každá položka obsahuje index sloupce a hodnotu. Obvykle se tyto položky uchovávají seřazené podle indexu sloupce pro rychlejší vyhledávání. Je to další formát vhodný pro inkrementální konstrukci matic.
Seznam souřadnic (COO)Upravit
COO ukládá seznam (řádek, sloupec, hodnota) tuplů. V ideálním případě jsou položky seřazeny nejprve podle indexu řádku a pak podle indexu sloupce, aby se zlepšila doba náhodného přístupu. Jedná se o další formát, který je vhodný pro inkrementální konstrukci matice.
Komprimovaný řídký řádek (CSR, CRS nebo formát Yale)Upravit
Komprimovaný řídký řádek (CSR) nebo komprimované řádkové úložiště (CRS) nebo formát Yale představuje matici M pomocí tří (jednorozměrných) polí, která obsahují nenulové hodnoty, resp. extenze řádků a indexy sloupců. Je podobný formátu COO, ale komprimuje řádkové indexy, odtud název. Tento formát umožňuje rychlý přístup k řádkům a násobení matice vektorem (Mx). Formát CSR se používá přinejmenším od poloviny 60. let, první úplný popis se objevil v roce 1967.
Formát CSR ukládá řídkou matici m × n M v řádkové podobě pomocí tří (jednorozměrných) polí (V, COL_INDEX, ROW_INDEX). Nechť NNZ označuje počet nenulových položek v M. (Všimněte si, že se zde používají indexy založené na nule.)
- Pole V a COL_INDEX mají délku NNZ a obsahují nenulové hodnoty, resp. indexy sloupců těchto hodnot.
- Pole ROW_INDEX má délku m + 1 a kóduje index ve V a COL_INDEX, kde začíná daný řádek. Posledním prvkem je NNZ , tj, fiktivní index ve V bezprostředně za posledním platným indexem NNZ – 1.
Například matice
( 5 0 0 0 0 8 0 0 0 0 0 3 0 0 0 6 0 0 ) {\displaystyle {\begin{pmatrix}5&0&0&0&0&8&0&0&0&0&0&3&0&0&6&0&0&0\\\end{pmatrix}}}.
je matice 4 × 4 se 4 nenulovými prvky, tedy
V = COL_INDEX = ROW_INDEX =
předpokládá nulově indexovaný jazyk.
Pro extrakci řádku nejprve definujeme:
row_start = ROW_INDEX row_end = ROW_INDEX
Poté vezmeme řezy z V a COL_INDEX počínaje řádkem_začátek a konče řádkem_konec.
Pro extrakci řádku 1 (druhého řádku) této matice nastavíme row_start=1 a row_end=2. Poté vytvoříme řezy V = a COL_INDEX = . Nyní víme, že v řádku 1 máme ve sloupci 1 jeden prvek s hodnotou 8.
V tomto případě reprezentace CSR obsahuje 13 záznamů oproti 16 v původní matici. Formát CSR šetří na paměti pouze v případě, že NNZ < (m (n – 1) – 1) / 2.Další příklad, matice
( 10 20 0 0 0 0 30 0 40 0 0 0 0 50 60 70 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}}}
je matice 4 × 6 (24 položek) s 8 nenulovými prvky, takže
V = COL_INDEX = ROW_INDEX =
celá je uložena jako 21 položek.
- ROW_INDEX rozdělí pole V na řádky:
(10, 20) (30, 40) (50, 60, 70) (80); - COL_INDEX zarovnává hodnoty do sloupců:
(10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).
Všimněte si, že v tomto formátu je první hodnota ROW_INDEX vždy nula a poslední je vždy NNZ, takže jsou v jistém smyslu zbytečné (i když v programovacích jazycích, kde je třeba explicitně ukládat délku pole, by NNZ zbytečná nebyla). Nicméně se tím vyhneme nutnosti řešit výjimečný případ při výpočtu délky každého řádku, protože to zaručuje, že vzorec ROW_INDEX – ROW_INDEX funguje pro libovolný řádek i. Navíc paměťové náklady tohoto redundantního uložení jsou pro dostatečně velkou matici pravděpodobně zanedbatelné.
Formáty (staré a nové) řídké matice Yale jsou případy schématu CSR. Starý formát Yale pracuje přesně tak, jak je popsáno výše, se třemi poli; nový formát kombinuje ROW_INDEX a COL_INDEX do jediného pole a diagonálu matice zpracovává samostatně.
U logických adjacenčních matic lze datové pole vynechat, protože k modelování binárního adjacenčního vztahu stačí existence záznamu v řádkovém poli.
Je pravděpodobně známý jako Yaleův formát, protože byl navržen ve zprávě Yale Sparse Matrix Package z katedry počítačových věd na Yaleově univerzitě z roku 1977.
Compressed sparse column (CSC nebo CCS)Upravit
CSC je podobný CSR s tím rozdílem, že hodnoty se čtou nejprve po sloupcích, pro každou hodnotu se ukládá řádkový index a ukazatele na sloupce. Například CSC je (val, row_ind, col_ptr), kde val je pole (shora dolů a pak zleva doprava) nenulových hodnot matice; row_ind jsou řádkové indexy odpovídající hodnotám a col_ptr je seznam indexů val, kde začíná každý sloupec. Název vychází ze skutečnosti, že informace o indexech sloupců jsou komprimovány oproti formátu COO. Pro konstrukci se obvykle používá jiný formát (LIL, DOK, COO). Tento formát je efektivní pro aritmetické operace, krájení sloupců a maticově-vektorové součinové operace. Viz scipy.sparse.csc_matrix. jedná se o tradiční formát pro zadání řídké matice v MATLABu (prostřednictvím funkce sparse).
.