O matrice este de obicei stocată ca o matrice bidimensională. Fiecare intrare în matrice reprezintă un element ai,j al matricei și este accesată prin cei doi indici i și j. În mod convențional, i este indicele de rând, numerotat de sus în jos, iar j este indicele de coloană, numerotat de la stânga la dreapta. Pentru o matrice m × n, cantitatea de memorie necesară pentru a stoca matricea în acest format este proporțională cu m × n (fără a lua în considerare faptul că trebuie stocate și dimensiunile matricei).

În cazul unei matrice rare, se pot realiza reduceri substanțiale ale necesarului de memorie prin stocarea numai a intrărilor care nu sunt zero. În funcție de numărul și distribuția intrărilor care nu sunt zero, se pot utiliza diferite structuri de date și se pot obține economii uriașe de memorie în comparație cu abordarea de bază. Compromisul este că accesarea elementelor individuale devine mai complexă și sunt necesare structuri suplimentare pentru a putea recupera matricea originală fără ambiguitate.

Formatele pot fi împărțite în două grupe:

• Cele care suportă modificarea eficientă, cum ar fi DOK (Dictionary of keys), LIL (List of lists) sau COO (Coordinate list). Acestea sunt utilizate de obicei pentru construirea matricelor.
• Cele care suportă accesul și operațiile matriciale eficiente, cum ar fi CSR (Compressed Sparse Row) sau CSC (Compressed Sparse Column).

Dicționar de chei (DOK)Edit

DOK constă într-un dicționar care mapează perechile de (rând, coloană) la valoarea elementelor. Elementele care lipsesc din dicționar sunt considerate a fi zero. Formatul este bun pentru construirea incrementală a unei matrice rare în ordine aleatorie, dar slab pentru iterația peste valorile care nu sunt zero în ordine lexicografică. De obicei, se construiește o matrice în acest format și apoi se convertește într-un alt format mai eficient pentru procesare.

Listă de liste (LIL)Edit

LIL stochează o listă pe rând, fiecare intrare conținând indicele coloanei și valoarea. De obicei, aceste intrări sunt păstrate sortate după indicele coloanei pentru o căutare mai rapidă. Acesta este un alt format bun pentru construcția matricei incrementale.

Lista de coordonate (COO)Edit

COO stochează o listă de tupluri (rând, coloană, valoare). În mod ideal, intrările sunt sortate mai întâi după indicele rândului și apoi după indicele coloanei, pentru a îmbunătăți timpii de acces aleatoriu. Acesta este un alt format care este bun pentru construcția incrementală a matricelor.

Format comprimat de rânduri rare (CSR, CRS sau format Yale)Editare

Formatul comprimat de rânduri rare (CSR) sau de stocare comprimată a rândurilor (CRS) sau formatul Yale reprezintă o matrice M prin trei matrici (unidimensionale), care conțin valorile care nu sunt zero, respectiv extensiile rândurilor și indicii coloanelor. Este similar cu COO, dar comprimă indicii rândurilor, de unde și numele. Acest format permite un acces rapid la rânduri și înmulțiri matrice-vector (Mx). Formatul CSR a fost utilizat cel puțin de la mijlocul anilor 1960, prima descriere completă apărând în 1967.

Formatul CSR stochează o matrice rară m × n M sub formă de rânduri folosind trei matrici (unidimensionale) (V, COL_INDEX, ROW_INDEX). Fie ca NNZ să denote numărul de intrări nenule din M. (Rețineți că aici se vor utiliza indici bazați pe zero.)

• Rețelele V și COL_INDEX sunt de lungime NNZ și conțin valorile nenule și, respectiv, indicii coloanelor acestor valori.

• Rețeaua ROW_INDEX este de lungime m + 1 și codifică indicele din V și COL_INDEX unde începe rândul dat. Ultimul element este NNZ , adică, indicele fictiv din V imediat după ultimul indice valid NNZ – 1.

De exemplu, matricea

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

este o matrice 4 × 4 cu 4 elemente diferite de zero, prin urmare

 V = COL_INDEX = ROW_INDEX = 

asumând un limbaj indexat cu zero.

Pentru a extrage un rând, mai întâi definim:

 row_start = ROW_INDEX row_end = ROW_INDEX

Apoi luăm felii din V și COL_INDEX începând de la row_start și terminând la row_end.

Pentru a extrage rândul 1 (al doilea rând) din această matrice se setează row_start=1 și row_end=2. Apoi facem feliile V = și COL_INDEX = . Acum știm că în rândul 1 avem un element în coloana 1 cu valoarea 8.

În acest caz, reprezentarea CSR conține 13 intrări, față de 16 în matricea originală. Formatul CSR economisește memorie numai atunci când NNZ < (m (n – 1) – 1) / 2.Un alt exemplu, matricea

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

este o matrice 4 × 6 (24 de intrări) cu 8 elemente care nu sunt zero, deci

 V = COL_INDEX = ROW_INDEX = 

Întregul este stocat ca 21 de intrări.

• ROW_INDEX împarte matricea V în rânduri: (10, 20) (30, 40) (50, 60, 70) (80);
• COL_INDEX aliniază valorile în coloane: .

Rețineți că, în acest format, prima valoare a ROW_INDEX este întotdeauna zero, iar ultima este întotdeauna NNZ, astfel încât acestea sunt, într-un anumit sens, redundante (deși în limbajele de programare în care lungimea tabloului trebuie să fie stocată în mod explicit, NNZ nu ar fi redundantă). Cu toate acestea, acest lucru evită necesitatea de a gestiona un caz excepțional la calcularea lungimii fiecărui rând, deoarece garantează că formula ROW_INDEX – ROW_INDEX funcționează pentru orice rând i. În plus, costul de memorie al acestei stocări redundante este probabil nesemnificativ pentru o matrice suficient de mare.

Formatele (vechi și nou) de matrice rare Yale sunt instanțe ale schemei CSR. Vechiul format Yale funcționează exact așa cum a fost descris mai sus, cu trei tablouri; noul format combină ROW_INDEX și COL_INDEX într-un singur tablou și tratează separat diagonala matricei.

Pentru matricele de adiacență logică, tabloul de date poate fi omis, deoarece existența unei intrări în tabloul de rânduri este suficientă pentru a modela o relație de adiacență binară.

Este probabil cunoscut sub numele de formatul Yale deoarece a fost propus în raportul Yale Sparse Matrix Package din 1977 al Departamentului de Informatică de la Universitatea Yale.

Compressed sparse column (CSC sau CCS)Edit

CSC este similar cu CSR, cu excepția faptului că valorile sunt citite mai întâi pe coloană, un index de rând este stocat pentru fiecare valoare și sunt stocați pointeri de coloană. De exemplu, CSC este (val, row_ind, col_ptr), unde val este o matrice de valori (de sus în jos, apoi de la stânga la dreapta) care nu sunt zero ale matricei; row_ind sunt indicii de rând corespunzători valorilor; și, col_ptr este lista de indici val de unde începe fiecare coloană. Denumirea se bazează pe faptul că informațiile privind indicii de coloană sunt comprimate în raport cu formatul COO. De obicei, se utilizează un alt format (LIL, DOK, COO) pentru construcție. Acest format este eficient pentru operațiile aritmetice, împărțirea coloanelor și produsele matrice-vector. A se vedea scipy.sparse.csc_matrix. acesta este formatul tradițional pentru specificarea unei matrice rare în MATLAB (prin intermediul funcției sparse).

.