Tutoriel Python & SciPy : le module sparse

Table des matières

Introduction

Tout d’abord, il faut dire qu’une matrice creuse ou sparse matrix est une matrice dont la plupart des éléments sont nuls et que seuls quelques éléments sont différents de zéro.

En Python, ces matrices creuses, basées principalement sur les tableaux NumPy, sont efficacement mises en œuvre dans le sous module scipy.sparse de la bibliothèque SciPy qui a été implémenté selon l’idée suivante : au lieu de stocker toutes les valeurs dans une matrice dense, il est plus simple de stocker les valeurs non nulles dans un format quelconque.

La meilleure performance en termes de temps et d'espace est obtenue lorsque nous stockons une matrice éparse avec le sous module scipy.sparse.

1. Représentation des matrices creuses

Pour stocker une matrice creuse, le sous module sparse de SciPy met à disposition les sept formats de représentation suivants :

Block sparse row matrix (BSR)
Coordinate list matrix (COO)
Compressed Sparse Column matrix (CSC)
Compressed Sparse Row matrix (CSR)
Dictionary Of Keys based sparse matrix (DOK)
Row-based linked list sparse matrix (LIL)
Sparse matrix with Diagonal storage (DIA)

Remarque :

Dans ce qui suit et pour construire une matrice à partir de trois tableaux on considère les notations suivantes :

Data[ :] représente les entrées de la matrice dans n’importe quel ordre.
Row[ :] représente les indices de ligne des entrées de la matrice.
Col[ :] représente les indices de colonne des entrées de la matrice.

Avec A [ row[k], col[k]] = data[k].

1.1. Block sparse row matrix (BSR)

Le format de stockage BSR est approprié pour les matrices creuses contenant des sous-matrices denses. Les matrices de blocs apparaissent souvent dans des discontinuités d’éléments finis à valeur vectorielle. Alors l’utilisation du format BSR est considérablement plus efficace pour de nombreuses opérations arithmétiques éparses que l’utilisation d’un autre format.

Exemple 1 :

Dans cet exemple on construit une matrice vide de format BSR.

Code :

from scipy.sparse import bsr_matrix
import numpy as np
b = bsr_matrix((4,4), dtype = np.int8).toarray()
print(b)

Résultat de l’exécution :

Exemple 2 :

Dans cet exemple on construit une matrice creuse de format BSR à partir des trois tableaux data, row et col.

Code :

from scipy.sparse import bsr_matrix
import numpy as np
row = np.array([0, 1, 3, 0, 0, 1, 3, 1])
col = np.array([0, 2, 3, 3, 1, 0, 2, 1])
data = np.array([3, 1, 8, 9, 1, 17, 5, 6])
b = bsr_matrix((data, (row, col)), shape = (4,4)).toarray()
print(b)

Résultat de l’exécution :

Exemple 3 :

Dans cet exemple on construit une matrice en utilisant la représentation standard du BSR où les indices des colonnes pour la ligne i sont stockés dans indices [indptr[i] : indptr[i + 1]] et leurs valeurs de bloc correspondantes sont stockées dans data [indptr[i] : indptr[i + 1]].

Code :

from scipy.sparse import bsr_matrix
import numpy as np
indptr = np.array([0, 1, 3, 6])
indices = np.array([0, 2, 2, 0, 1, 2])
data = np.array([1, 7, 9, 4, 10, 2]).repeat(4).reshape(6, 2, 2)
b = bsr_matrix((data, indices, indptr), shape = (6, 6)).toarray()
print(b)

Résultat de l’exécution :

1.2. Coordinate list matrix (COO)

Le COO est un format rapide de construction de matrices creuses. Cependant pour des opérations arithmétiques et vectorielles plus rapides, il est préférable de convertir la matrice creuse au format CSR ou CSC.

Exemple 4 :

Dans cet exemple on construit une matrice vide de format COO.

Code :

from scipy.sparse import coo_matrix
import numpy as np
a = coo_matrix((4,4), dtype = np.int8).toarray()
print(a)

Résultat de l’exécution :

Exemple 5 :

Dans cet exemple on construit une matrice creuse de format COO à partir des trois tableaux data, row et col.

Code :

from scipy.sparse import coo_matrix
import numpy as np
row = np.array([0, 1, 3, 0])
col = np.array([0, 2, 1, 2])
data = np.array([3, 1, 8, 9])
a = coo_matrix((data, (row, col)), shape = (4, 4)).toarray()
print(a)

Résultat de l’exécution :

1.3. Compressed Sparse format

Les formats Compressed Sparse Column et Compressed Sparse Row sont les plus utilisés et les plus connus. Ces formats sont utilisés pour les tâches WORM (Write Once Read Many), c’est-à-dire écrire une fois et lire autant de fois souhaitée.

csc_matrix( (data, indices, indptr), [shape = (a,b)] ) est la représentation standard du format CSC (idem pour le format CSR, on change juste crc_matrix par csr_matrix) où les indices des colonnes pour la ligne i sont stockés dans indices [indptr[i] : indptr[i + 1]] et leurs valeurs de bloc correspondantes sont stockées dans data [indptr[i] : indptr[i + 1]].

1.3.1. Compressed Sparse Column matrix (CSC)

Exemple 6 :

Dans cet exemple on construit une matrice vide de format CSC.

Code :

import numpy as np
from scipy.sparse import csc_matrix
c = csc_matrix((4, 4), dtype = np.int8).toarray()
print(c)

Résultat de l’exécution :

Exemple 7 :

Dans cet exemple on construit une matrice creuse de format CSC à partir des trois tableaux data, row et col.

Code :

import numpy as np
from scipy.sparse import csc_matrix
row = np.array([0, 1, 3, 0])
col = np.array([0, 2, 1, 2])
data = np.array([3, 1, 8, 9])
c = csc_matrix((data, (row, col)), shape=(4, 4)).toarray()
print(c)

Résultat de l’exécution :

Exemple 8 :

Dans cet exemple on construit une matrice en utilisant la représentation standard du CSC.

Code :

from scipy.sparse import csc_matrix
import numpy as np
indptr = np.array([0, 3, 2, 6])
indices = np.array([0, 2, 0, 3, 2, 1])
data = np.array([1, 7, 9, 4, 10, 2])
c = csc_matrix((data, indices, indptr), shape = (3, 3)).toarray()
print(c)

Résultat de l’exécution :

1.3.2. Compressed Sparse Row matrix (CSR)

Exemple 9 :

Dans cet exemple on construit une matrice vide de format CSR.

Code :

from scipy.sparse import csr_matrix
import numpy as np
d = csr_matrix((4, 4), dtype = np.int8).toarray()
print(d)

Résultat de l’exécution :

Exemple 10 :

Dans cet exemple on construit une matrice creuse de format CSR à partir des trois tableaux data, row et col.

Code :

from scipy.sparse import csr_matrix
import numpy as np
row = np.array([0, 1, 3, 0])
col = np.array([0, 2, 1, 2])
data = np.array([3, 1, 8, 9])
c = csr_matrix((data, (row, col)), shape=(4, 4)).toarray()
print(c)

Résultat de l’exécution :

Exemple 11 :

Dans cet exemple on construit une matrice en utilisant la représentation standard du CSR.

Code :

from scipy.sparse import csr_matrix
import numpy as np
indptr = np.array([0, 3, 2, 6])
indices = np.array([0, 2, 0, 3, 2, 1])
data = np.array([1, 7, 9, 4, 10, 2])
c = csr_matrix((data, indices, indptr), shape = (3, 3)).toarray()
print(c)

Résultat de l’exécution :

1.4. Dictionary Of Keys based sparse matrix (DOK)

Le format DOK permet un accès rapide et efficace aux éléments individuels. Certes, il n’autorise pas de doublons.

Une fois une matrice est construite selon ce format elle peut être convertie efficacement en une matrice creuse de format COO.

Exemple 12 :

On construit dans cet exemple une matrice de format DOK.

Code :

from scipy.sparse import dok_matrix
import numpy as np
e = dok_matrix((4, 4), dtype = np.int8).toarray()
for i in range(4):
for j in range(4):
e[i, j] = i + j
print(e)

Résultat de l’exécution :

1.5. Row-based linked list sparse matrix (LIL)

Le LIL est un format pratique pour construire des matrices creuses. Cependant pour des opérations arithmétiques et vectorielles plus rapides il est préférable de convertir la matrice creuse au format CSR ou CSC.

Remarque :

Pour construire des matrices creuses de grande taille, l’utilisation du Format COO est recommandée.

Exemple 13 :

On construit dans cet exemple une matrice de format LIL.

Code :

from scipy.sparse import lil_matrix
import numpy as np
l = lil_matrix((4, 4), dtype = np.int8).toarray()
for i in range(4):
for j in range(4):
l[i, j] = i + j
print(l)

Résultat de l’exécution :

1.6. Sparse matrix with Diagonal storage (DIA)

Le format DIA est utilisé pour construire des matrices diagonales.

Pour stocker une matrice selon ce format deux tableaux sont utilisés, le premier pour stocker les données (data [k :]) et le second pour les décalages diagonaux (offsets[k]).

Exemple 14 :

Dans cet exemple, on construit une matrice vide de format DIA.

Code :

from scipy.sparse import dia_matrix
import numpy as np
w = dia_matrix( (4, 4), dtype = np.int8).toarray()
print(w)

Résultat de l’exécution :

Exemple 15 :

On construit dans cet exemple une matrice de format DIA.

Code :

from scipy.sparse import dia_matrix
import numpy as np
data = np.array([[7, 15, 6, 4]]).repeat(3, axis = 0)
offsets = np.array([0, -1, 2])
w = dia_matrix((data, offsets), shape = (4, 4)).toarray()
print(w)

Résultat de l’exécution :

Conclusion

Dans ce tutoriel nous avons vu les différents formats de construction de matrices éparses contenues dans le sous-module scipy.sparse de la bibliothèque SciPy.

Article publié le 01 Novembre 2020par Imane BENHMIDOU