Matrices creuses

Ne stocker que ce qui n'est pas nul

Beaucoup de grandes matrices sont presque entièrement nulles. Une grille pour valoriser une option a une ligne par niveau de prix, et chaque ligne ne touche que ses deux voisines. Une telle matrice est dite creuse. Stocker chaque zéro gaspille mémoire et temps. scipy.sparse ne garde que les entrées non nulles. Le format csr_matrix (ligne creuse compressée) utilise trois listes. data contient les valeurs non nulles ligne par ligne, indices la colonne de chaque valeur, et indptr dit où chaque ligne commence et finit dans data : la ligne $i$ est data[indptr[i]:indptr[i+1]]. Le dernier nombre de indptr est le nombre de valeurs non nulles, nnz.

Des formats différents conviennent à des tâches différentes. coo_matrix stocke de simples triplets (ligne, colonne, valeur) et c'est la façon facile de construire une matrice. csr_matrix est rapide pour les tranches de lignes et pour le produit $A\mathbf x$ , qui coûte environ nnz multiplications au lieu de $n^2$ . csc_matrix est la même idée par colonnes, et dia_matrix stocke des diagonales, idéal pour les matrices bandes. Pour un système $A\mathbf x=\mathbf b$ , sparse.linalg.spsolve exploite les zéros pour être bien plus rapide qu'une résolution dense. Le creux n'est pas toujours meilleur : si plus d'un tiers environ des entrées sont non nulles, la comptabilité coûte plus qu'elle ne rapporte. En finance, la sparsité apparaît dans les grilles de valorisation, dans les modèles à facteurs où la plupart des expositions sont nulles, et quand on ne garde que les fortes corrélations.

A\mathbf x\ \text{costs}\ \approx \mathrm{nnz}\ \text{multiplications},\qquad \text{density}=\frac{\mathrm{nnz}}{n^{2}},\qquad \text{row } i=\texttt{data}[\texttt{indptr}[i]:\texttt{indptr}[i+1]]

(1)

Lire une matrice CSRPrenons la matrice

4\times4

de lignes

(5;0;0;1)

(0;0;2;0)

(0;0;0;0)

(3;0;0;4)

. En CSR, data=[5,1,2,3,4], indices=[0,3,2,0,3] et indptr=[0,2,3,3,5]. La ligne

2

est vide car indptr[2]=indptr[3]=3, et nnz=5. Multiplier par

(1;1;1;1)

additionne chaque ligne, ce qui donne

(6;2;0;7)

avec seulement

5

multiplications. Une matrice tridiagonale avec

n=1000

, comme une grille de valorisation aux différences finies, a

2\,998

valeurs non nulles sur

1\,000\,000

entrées, soit une densité de

0{,}30\%

. Elle demande environ

40

Ko en CSR contre

8

Mo en dense. Sur données réelles, les corrélations de

55

actions du fichier de prix partagé forment une matrice

55\times55

. Ne garder que les entrées avec

|\rho|>0{,}5

laisse

249

des

3\,025

entrées, soit

8{,}2\%

, et la copie CSR prend

3{,}2

Ko contre

24{,}2

Ko en dense. À

|\rho|>0{,}6

, il n'en reste que

4{,}3\%

Trois listes : data, indices et indptr décrivent une matrice CSR, et indptr[-1] est le nombre de valeurs non nulles.
Construire en COO, calculer en CSR : les triplets sont faciles à assembler, le stockage par lignes est rapide pour produits et résolutions.
Le creux ne paie que s'il y a surtout des zéros : une matrice dense vaut mieux quand beaucoup d'entrées sont non nulles.

Lab : ce qui est noté

Compter les valeurs non nulles10 pts
Combien de valeurs dans une ligne10 pts
La densité d'une grille10 pts
Un produit creux15 pts
Quel format pour quelle tâche15 pts
Un système tridiagonal10 pts
Quand le creux rapporte et quand non30 pts

Ne stocker que ce qui n'est pas nul

A\mathbf x\ \text{costs}\ \approx \mathrm{nnz}\ \text{multiplications},\qquad \text{density}=\frac{\mathrm{nnz}}{n^{2}},\qquad \text{row } i=\texttt{data}[\texttt{indptr}[i]:\texttt{indptr}[i+1]]

(1)

Lire une matrice CSRPrenons la matrice

4\times4

de lignes

(5;0;0;1)

(0;0;2;0)

(0;0;0;0)

(3;0;0;4)

. En CSR, data=[5,1,2,3,4], indices=[0,3,2,0,3] et indptr=[0,2,3,3,5]. La ligne

2

est vide car indptr[2]=indptr[3]=3, et nnz=5. Multiplier par

(1;1;1;1)

additionne chaque ligne, ce qui donne

(6;2;0;7)

avec seulement

5

multiplications. Une matrice tridiagonale avec

n=1000

, comme une grille de valorisation aux différences finies, a

2\,998

valeurs non nulles sur

1\,000\,000

entrées, soit une densité de

0{,}30\%

. Elle demande environ

40

Ko en CSR contre

8

Mo en dense. Sur données réelles, les corrélations de

55

actions du fichier de prix partagé forment une matrice

55\times55

. Ne garder que les entrées avec

|\rho|>0{,}5

laisse

249

des

3\,025

entrées, soit

8{,}2\%

, et la copie CSR prend

3{,}2

Ko contre

24{,}2

Ko en dense. À

|\rho|>0{,}6

, il n'en reste que

4{,}3\%

Trois listes : data, indices et indptr décrivent une matrice CSR, et indptr[-1] est le nombre de valeurs non nulles.
Construire en COO, calculer en CSR : les triplets sont faciles à assembler, le stockage par lignes est rapide pour produits et résolutions.
Le creux ne paie que s'il y a surtout des zéros : une matrice dense vaut mieux quand beaucoup d'entrées sont non nulles.

Lab : ce qui est noté

Compter les valeurs non nulles10 pts
Combien de valeurs dans une ligne10 pts
La densité d'une grille10 pts
Un produit creux15 pts
Quel format pour quelle tâche15 pts
Un système tridiagonal10 pts
Quand le creux rapporte et quand non30 pts

Ne stocker que ce qui n'est pas nul

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.

Matrices creuses

Ne stocker que ce qui n'est pas nul

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.