Una matrice è tipicamente memorizzata come una matrice bidimensionale. Ogni voce nella matrice rappresenta un elemento ai,j della matrice ed è accessibile tramite i due indici i e j. Convenzionalmente, i è l’indice di riga, numerato dall’alto in basso, e j è l’indice di colonna, numerato da sinistra a destra. Per una matrice m × n, la quantità di memoria richiesta per memorizzare la matrice in questo formato è proporzionale a m × n (trascurando il fatto che anche le dimensioni della matrice devono essere memorizzate).

Nel caso di una matrice rada, sostanziali riduzioni dei requisiti di memoria possono essere realizzate memorizzando solo le voci non zero. A seconda del numero e della distribuzione delle voci non nulle, si possono usare diverse strutture di dati e ottenere enormi risparmi di memoria rispetto all’approccio di base. Il compromesso è che l’accesso ai singoli elementi diventa più complesso e sono necessarie strutture aggiuntive per poter recuperare la matrice originale senza ambiguità.

I formati possono essere divisi in due gruppi:

• Quelli che supportano una modifica efficiente, come DOK (Dizionario di chiavi), LIL (Lista di liste), o COO (Lista di coordinate). Questi sono tipicamente usati per costruire le matrici.
• Quelli che supportano un accesso efficiente e operazioni di matrice, come CSR (Compressed Sparse Row) o CSC (Compressed Sparse Column).

Dizionario di chiavi (DOK)Edit

DOK consiste in un dizionario che mappa le coppie (riga, colonna) al valore degli elementi. Gli elementi che mancano dal dizionario sono presi come zero. Il formato è buono per costruire incrementalmente una matrice sparsa in ordine casuale, ma povero per iterare su valori non nulli in ordine lessicografico. Uno tipicamente costruisce una matrice in questo formato e poi la converte in un altro formato più efficiente per l’elaborazione.

Lista di liste (LIL)Edit

LIL memorizza una lista per riga, con ogni voce contenente l’indice di colonna e il valore. Tipicamente, queste voci sono tenute ordinate per indice di colonna per una ricerca più veloce. Questo è un altro formato buono per la costruzione di matrici incrementali.

Lista di coordinate (COO)Edit

COO memorizza una lista di tuple (riga, colonna, valore). Idealmente, le voci sono ordinate prima per indice di riga e poi per indice di colonna, per migliorare i tempi di accesso casuale. Questo è un altro formato che va bene per la costruzione di matrici incrementali.

Fila sparsa compressa (CSR, CRS o formato Yale)Edit

La fila sparsa compressa (CSR) o la memorizzazione della fila compressa (CRS) o il formato Yale rappresentano una matrice M da tre matrici (unidimensionali), che contengono rispettivamente valori non nulli, le estensioni delle righe e gli indici di colonna. È simile a COO, ma comprime gli indici di riga, da cui il nome. Questo formato permette un accesso veloce alle righe e alle moltiplicazioni matrice-vettore (Mx). Il formato CSR è in uso almeno dalla metà degli anni ’60, con la prima descrizione completa che appare nel 1967.

Il formato CSR memorizza una matrice rada m × n M in forma di riga usando tre matrici (unidimensionali) (V, COL_INDEX, ROW_INDEX). Lasciamo che NNZ denoti il numero di voci non nulle in M. (Si noti che gli indici basati su zero sono usati qui.)

• Gli array V e COL_INDEX sono di lunghezza NNZ, e contengono rispettivamente i valori non nulli e gli indici di colonna di quei valori.

• L’array ROW_INDEX è di lunghezza m + 1 e codifica l’indice in V e COL_INDEX dove inizia la riga data. L’ultimo elemento è NNZ , cioè, l’indice fittizio in V immediatamente dopo l’ultimo indice valido NNZ – 1.

Per esempio, la matrice

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

è una matrice 4 × 4 con 4 elementi non zero, quindi

 V = COL_INDEX = ROW_INDEX = 

assumendo un linguaggio indicizzato a zero.

Per estrarre una riga, definiamo prima:

 row_start = ROW_INDEX row_end = ROW_INDEX

Poi prendiamo delle fette da V e COL_INDEX partendo da row_start e finendo a row_end.

Per estrarre la riga 1 (la seconda riga) di questa matrice impostiamo row_start=1 e row_end=2. Poi facciamo le fette V = e COL_INDEX = . Ora sappiamo che nella riga 1 abbiamo un elemento nella colonna 1 con valore 8.

In questo caso la rappresentazione CSR contiene 13 voci, rispetto alle 16 della matrice originale. Il formato CSR risparmia memoria solo quando NNZ < (m (n – 1) – 1) / 2.Un altro esempio, la matrice

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

è una matrice 4 × 6 (24 voci) con 8 elementi non nulli, quindi

 V = COL_INDEX = ROW_INDEX = 

il tutto è memorizzato come 21 voci.

• ROW_INDEX divide l’array V in righe: (10, 20) (30, 40) (50, 60, 70) (80);
• COL_INDEX allinea i valori nelle colonne: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Nota che in questo formato, il primo valore di ROW_INDEX è sempre zero e l’ultimo è sempre NNZ, quindi sono in un certo senso ridondanti (anche se nei linguaggi di programmazione dove la lunghezza dell’array deve essere memorizzata esplicitamente, NNZ non sarebbe ridondante). Tuttavia, questo evita la necessità di gestire un caso eccezionale quando si calcola la lunghezza di ogni riga, poiché garantisce che la formula ROW_INDEX – ROW_INDEX funzioni per qualsiasi riga i. Inoltre, il costo di memoria di questa memorizzazione ridondante è probabilmente insignificante per una matrice sufficientemente grande.

I formati (vecchio e nuovo) della matrice sparsa Yale sono istanze dello schema CSR. Il vecchio formato Yale funziona esattamente come descritto sopra, con tre matrici; il nuovo formato combina ROW_INDEX e COL_INDEX in una singola matrice e gestisce la diagonale della matrice separatamente.

Per le matrici di adiacenza logica, la matrice dei dati può essere omessa, poiché l’esistenza di una voce nella matrice delle righe è sufficiente per modellare una relazione di adiacenza binaria.

È probabilmente conosciuto come il formato Yale perché è stato proposto nel 1977 nel rapporto Yale Sparse Matrix Package del Dipartimento di Informatica dell’Università di Yale.

Colonna sparsa compressa (CSC o CCS)Edit

CSC è simile a CSR tranne che i valori sono letti prima per colonna, un indice di riga è memorizzato per ogni valore, e i puntatori di colonna sono memorizzati. Per esempio, CSC è (val, row_ind, col_ptr), dove val è un array dei valori (dall’alto in basso, poi da sinistra a destra) non nulli della matrice; row_ind sono gli indici di riga corrispondenti ai valori; e, col_ptr è la lista degli indici di val dove inizia ogni colonna. Il nome si basa sul fatto che le informazioni sugli indici di colonna sono compresse rispetto al formato COO. In genere si usa un altro formato (LIL, DOK, COO) per la costruzione. Questo formato è efficiente per le operazioni aritmetiche, il taglio delle colonne e i prodotti matrice-vettore. Vedi scipy.sparse.csc_matrix.Questo è il formato tradizionale per specificare una matrice sparsa in MATLAB (tramite la funzione sparse).