Macierz jest zwykle przechowywana jako tablica dwuwymiarowa. Każdy wpis w tablicy reprezentuje element ai,j macierzy i jest dostępny przez dwa indeksy i oraz j. Konwencjonalnie, i jest indeksem wiersza, numerowanym od góry do dołu, a j jest indeksem kolumny, numerowanym od lewej do prawej. Dla macierzy m × n, ilość pamięci wymaganej do przechowywania macierzy w tym formacie jest proporcjonalna do m × n (pomijając fakt, że wymiary macierzy również muszą być przechowywane).

W przypadku macierzy rzadkiej, znaczne zmniejszenie wymagań pamięciowych można zrealizować poprzez przechowywanie tylko niezerowych wpisów. W zależności od liczby i rozmieszczenia niezerowych wpisów, można użyć różnych struktur danych i uzyskać ogromne oszczędności w pamięci w porównaniu do podstawowego podejścia. Kompromisem jest to, że dostęp do poszczególnych elementów staje się bardziej złożony i potrzebne są dodatkowe struktury, aby móc jednoznacznie odzyskać oryginalną macierz.

Formaty można podzielić na dwie grupy:

• Te, które wspierają wydajną modyfikację, takie jak DOK (Dictionary of keys), LIL (List of lists), lub COO (Coordinate list). Są one zwykle używane do konstruowania macierzy.
• Te, które wspierają wydajny dostęp i operacje na macierzach, takie jak CSR (Compressed Sparse Row) lub CSC (Compressed Sparse Column).

Słownik kluczy (DOK)Edycja

DOK składa się ze słownika, który mapuje pary (wiersz, kolumna) na wartości elementów. Elementy, których brakuje w słowniku, są przyjmowane jako zero. Format ten jest dobry do przyrostowego konstruowania nieliczbowych macierzy w przypadkowej kolejności, ale kiepski do iteracji nad niezerowymi wartościami w porządku leksykograficznym. Zazwyczaj konstruuje się macierz w tym formacie, a następnie konwertuje do innego, bardziej wydajnego formatu do przetwarzania.

Lista list (LIL)Edycja

LIL przechowuje jedną listę na wiersz, z każdym wpisem zawierającym indeks kolumny i wartość. Zazwyczaj te wpisy są przechowywane posortowane według indeksu kolumny, aby szybciej wyszukiwać. Jest to kolejny format dobry do przyrostowej konstrukcji macierzy.

Lista współrzędnych (COO)Edycja

COO przechowuje listę tupli (wiersz, kolumna, wartość). Idealnie, wpisy są sortowane najpierw według indeksu wiersza, a następnie według indeksu kolumny, aby poprawić losowe czasy dostępu. Jest to kolejny format, który jest dobry do przyrostowej konstrukcji macierzy.

Skompresowany rzadki rząd (CSR, CRS lub format Yale)Edycja

Skompresowany rzadki rząd (CSR) lub skompresowane przechowywanie wierszy (CRS) lub format Yale reprezentuje macierz M przez trzy (jednowymiarowe) tablice, które odpowiednio zawierają wartości niezerowe, ekstensje wierszy i indeksy kolumn. Jest on podobny do COO, ale kompresuje indeksy wierszy, stąd nazwa. Format ten pozwala na szybki dostęp do wierszy i mnożenie macierzowo-wektorowe (Mx). Format CSR jest używany co najmniej od połowy lat sześćdziesiątych, a jego pierwszy pełny opis pojawił się w 1967 roku.

Format CSR przechowuje nieliczbową macierz m × n M w postaci wierszowej przy użyciu trzech (jednowymiarowych) tablic (V, COL_INDEX, ROW_INDEX). Niech NNZ oznacza liczbę niezerowych wpisów w M. (Zauważ, że używane są indeksy oparte na zerze.)

• Tablice V i COL_INDEX mają długość NNZ i zawierają odpowiednio wartości niezerowe i indeksy kolumn tych wartości.

• Tablica ROW_INDEX ma długość m + 1 i koduje indeks w V i COL_INDEX, gdzie zaczyna się dany wiersz. Ostatnim elementem jest NNZ , tzn, fikcyjny indeks w V bezpośrednio za ostatnim prawidłowym indeksem NNZ – 1.

Na przykład macierz

( 5 0 0 0 0 8 0 0 0 0 3 0 0 6 0 0 ) {begin{pmatrix}5&0&0&8&0&0&0&3&0&6&0&0&end{pmatrix}}

jest macierzą 4 × 4 z 4 niezerowymi elementami, stąd

 V = COL_INDEX = ROW_INDEX = 

zakładając zerową indeksację języka.

Aby wyodrębnić rząd, najpierw definiujemy:

 row_start = ROW_INDEX row_end = ROW_INDEX

Potem bierzemy plasterki z V i COL_INDEX zaczynając od row_start i kończąc na row_end.

Aby wyodrębnić rząd 1 (drugi rząd) tej macierzy ustawiamy row_start=1 i row_end=2. Następnie wykonujemy plasterki V = i COL_INDEX = . Teraz wiemy, że w wierszu 1 mamy jeden element w kolumnie 1 o wartości 8.

W tym przypadku reprezentacja CSR zawiera 13 wpisów, w porównaniu do 16 w oryginalnej macierzy. Format CSR oszczędza pamięć tylko wtedy, gdy NNZ < (m (n – 1) – 1) / 2.Inny przykład, macierz

( 10 20 0 0 0 0 0 30 0 40 0 0 0 0 50 60 70 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}}}

jest macierzą 4 × 6 (24 wpisy) z 8 niezerowymi elementami, więc

 V = COL_INDEX = ROW_INDEX = 

całość jest przechowywana jako 21 wpisów.

• ROW_INDEX dzieli tablicę V na wiersze: (10, 20) (30, 40) (50, 60, 70) (80);
• COL_INDEX wyrównuje wartości w kolumnach: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Zauważ, że w tym formacie pierwsza wartość ROW_INDEX jest zawsze zerem, a ostatnia zawsze NNZ, więc są one w pewnym sensie nadmiarowe (choć w językach programowania, w których długość tablicy musi być jawnie przechowywana, NNZ nie byłoby nadmiarowe). Niemniej jednak, pozwala to uniknąć potrzeby obsługi wyjątkowego przypadku podczas obliczania długości każdego wiersza, ponieważ gwarantuje, że formuła ROW_INDEX – ROW_INDEX działa dla dowolnego wiersza i. Ponadto koszt pamięci tego nadmiarowego przechowywania jest prawdopodobnie nieistotny dla wystarczająco dużej macierzy.

Formaty (stary i nowy) Yale sparse matrix są instancjami schematu CSR. Stary format Yale działa dokładnie tak, jak opisano powyżej, z trzema tablicami; nowy format łączy ROW_INDEX i COL_INDEX w jedną tablicę i obsługuje przekątną macierzy oddzielnie.

Dla logicznych macierzy adjacency, tablica danych może być pominięta, ponieważ istnienie wpisu w tablicy wierszy jest wystarczające do modelowania binarnej relacji adjacency.

Jest on prawdopodobnie znany jako format Yale, ponieważ został zaproponowany w raporcie Yale Sparse Matrix Package z 1977 roku z Department of Computer Science na Yale University.

Compressed sparse column (CSC lub CCS)Edit

CSC jest podobny do CSR z wyjątkiem tego, że wartości są odczytywane najpierw według kolumn, indeks wiersza jest przechowywany dla każdej wartości, a wskaźniki kolumn są przechowywane. Na przykład, CSC jest (val, row_ind, col_ptr), gdzie val jest tablicą (od góry do dołu, potem od lewej do prawej) niezerowych wartości macierzy; row_ind jest indeksem wiersza odpowiadającym wartościom; i, col_ptr jest listą indeksów val, gdzie zaczyna się każda kolumna. Nazwa jest oparta na fakcie, że informacje o indeksie kolumny są skompresowane w stosunku do formatu COO. Zazwyczaj do konstrukcji używa się innego formatu (LIL, DOK, COO). Format ten jest wydajny dla operacji arytmetycznych, krojenia kolumn i produktów macierzowo-wektorowych. Zobacz scipy.sparse.csc_matrix.Jest to tradycyjny format określania macierzy rzadkiej w MATLABie (poprzez funkcję sparse).