La matrice sparsa su Matlab

In questa lezione online ti spiego come creare le matrici sparse tramite Matlab.

Cos'è una matrice sparsa? Le matrici sparse ti permettono di generare matrici molto grandi occupando una minore quantità di memoria del computer. Ad esempio, se crei una matrice con molti valori costanti (es. zero) ripeti gli stessi valori in più elementi. Quindi, occupi inutilmente una gran parte della memoria. $$ M = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix} $$ Per ridurre la quantità di memoria occupata puoi generare la stessa matrice come matrice sparsa (sparse matrix) dove i dati sono compressi perché i valori nulli sono ignorati.

In Matlab puoi usare le matrici sparse per creare matrici identità e matrici diagonali compresse.

Le matrice identità sparse

Ti faccio un esempio pratico

Crea una matrice identità usando la funzione eye(4)

>> eye(4)
ans =
Diagonal Matrix
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

Nella matrice ci sono ben 12 zeri e 4 uno.

Quindi, gran parte dello spazio nella matrice (12 elementi su 16) è occupato inutilmente dallo zero.

Ora crea la stessa matrice identità usando la tecnica delle matrici sparse tramite il comando speye(4)

>> speye(4)
ans =
Compressed Column Sparse (rows = 4, cols = 4, nnz = 4 [25%])
(1, 1) -> 1
(2, 2) -> 1
(3, 3) -> 1
(4, 4) -> 1

Nella matrice sparsa Matlab elenca solo le posizioni (riga, colonna) della matrice in cui ci sono i valori diversi da zero, occupando una minore quantità di memoria.

Per questa ragione si chiama matrice "sparsa".

Nota. La matrice sparsa occupa una minore quantità di memoria perché considera solo le informazioni utili. In una matrice identità gli zero sono degli elementi ininfluenti nel calcolo matriciale. Pertanto sono eliminati. Questo permette di ridurre lo spazio di memoria occupato (complessità spaziale) e riduce il tempo di esecuzione dei calcoli (complessità temporale).

Puoi usare la matrice sparsa che hai appena creato nei calcoli come se fosse una matrice normale.

Ad esempio, crea una matrice quadrata M con quattro righe e quattro colonne

>> M=[1 2 3 4;5 6 7 8; 9 0 1 2; 3 4 5 6]
M =
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6

Poi moltiplica la matrice M per una matrice identità di dimensione 4

>> M*eye(4)
ans =
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6

Ora moltiplica la stessa matrice M per la matrice identità sparsa di dimensione 4

>> M*speye(4)
ans =
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6

Come puoi vedere il risultato finale delle operazioni M*eye(4) e M*speye(4) è sempre lo stesso.

Nell'operazione con la matrice sparsa M*speye(4) hai però ottenuto il risultato più velocemente usando una minore quantità della memoria del computer.

Le matrici diagonali sparse

In Matlab c'è un'apposita funzione per creare le matrici diagonali sparse. Si tratta della funzione spdiags()

spdiags(v,i,r,c)

• Il primo parametro (v) è un vettore colonna con gli elementi da inserire sulla diagonale
• il secondo parametro (i) è l'indice della diagonale dove vuoi inserire gli elementi. Di default è 0 dove zero è la diagonale principale)
• il terzo (r) e il quarto (c) parametro sono il numero di righe e colonne della matrice sparsa da creare

Ad esempio, digita spdiags([1;2;3],0,3,3) per creare una matrice diagonale sparsa 3x3

>> spdiags([1;2;3],0,3,3)
ans =
Compressed Column Sparse (rows = 3, cols = 3, nnz = 3 [33%])

(1, 1) -> 1
(2, 2) -> 2
(3, 3) -> 3

Matlab inserisce gli elementi del vettore [1;2;3] nella diagonale principale di una matrice 3x3.

Il risultato in output è una sparse matrix della matrice diagonale

$$ M = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \\ \end{pmatrix} $$

Come creare una matrice sparsa manualmente

In Matlab puoi anche definire una matrice sparsa indicando in un elenco la posizione di ogni valore non nullo della matrice.

Ad esempio, crea una sparse matrix a partire da questa matrice

$$ M = \begin{pmatrix} 3 & 0 & 1 \\ 0 & 1 & 2 \\ 4 & 0 & 0 \end{pmatrix} $$

Scrivi in un array l'elenco dei valori non nulli della matrice specificando la riga, la colonna e il valore

>> v = [1 1 3; 1 3 1; 2 2 1; 2 3 2; 3 1 4]
v =
1 1 3
1 3 1
2 2 1
2 3 2
3 1 4

Ogni riga dell'array indica la posizione (riga e colonna) e il un valore di un elemento non nullo della matrice

Spiegazione. Il primo elemento non nullo (3) della matrice si trova nella prima riga e prima colonna (1,1). E' l'elemento scritto in rosso nell'esempio qui sotto. Per indicare questo elemento nell'elenco della sparse matrix devi scrivere 1 1 3 in una riga dell'array. E via dicendo.

Una volta definito l'array con l'elenco dei valori non nulli, crea la matrice sparsa usando la funzione spconvert()

>> spconvert(v)

Il risultato è una matrice sparsa con i valori nelle posizioni che hai indicato.

ans =
Compressed Column Sparse (rows = 3, cols = 3, nnz = 5 [56%])
(1, 1) -> 3
(3, 1) -> 4
(2, 2) -> 1
(1, 3) -> 1
(2, 3) -> 2

Quando creai l'array puoi definire gli elementi non nulli della matrice in qualsiasi ordine.

Puoi anche indicare più volte la stessa posizione della matrice usando valori diversi.

Nota. Se definisci più volte la stessa posizione della matrice nell'array, Matlab somma tra loro tutti i valori tra loro. Ad esempio, crea una matrice sparsa indicando nella posizione (1,1) sia il valore 2 che il valore 3. Nella posizione (1,1) della matrice Matlab considera la somma dei due valori 2+3=5

Questo metodo ti permette anche di generare una matrice sparsa con i numeri complessi.