Définition

Une matrice est qualifiée de 'creuse' (anglais: sparse) si elle comporte majoritairement des coefficients nuls, ou (autrement dit) si le pourcentage des coefficients non nuls est faible (ceci est évidemment subjectif).

Exemple

Une image scannée haute définition 'au trait' (noir et blanc sans nuances de gris) se présente comme une très grosse matrice binaire, avec des codes (disons 0 pour la couleur dominante blanche et 1 pour le noir correspondant aux pixels informatifs (écriture, dessin)), peut être considérée comme une matrice creuse.
En général la répartition des coefficients non nuls n'est pas aléatoire, on observe parfois des regroupements autours de la diagonale.
Dans le cas d'une image au trait la présence d'un pixel noir augmente la probabilité de présence d'un autre pixel noir dans les cellules voisines, cela est dû au fait que l'écriture, le dessin, procèdent par des tracés continus.

Image: http://fr.wikipedia.org/wiki/Fichier:Finite_element_sparse_matrix.png

Représentation en mémoire

Il est ridicule de mémoriser tous les m × n coefficients d'une matrice creuse de type (m,n). Il suffit d'en mémoriser les coefficients non nuls. Plusieurs types de représentation sont possibles: La représentation Python COO est facile à comprendre, on caractérise une matrice creuse par 3 listes: On obtient la matrice en lisant ces trois lignes en colonnes. Cependant ce type de représentation ne renseigne en rien sur le type de la matrice. Ce type de représentation n'est évidemment pas optimal.
Un exemple d'une représentation 'standard' est le format Yale Sparse Matrix (version old). Il stocke une matrice M de taille m×n sous la forme de trois tableaux unidimensionnels. Si on note NNN le nombre d'entrées non nulles dans la matrice M.
Par exemple:
[ 1 2 0 0 0 0 0 0 0 0 0 1]
[ 0 3 9 0 0 0 0 0 0 0 0 0]
[ 0 1 4 0 0 0 0 0 0 0 0 0]
est représenté par:
A = [ 1 2 1 3 9 1 4 ]
IA = [ 1 4 6 8 ]
JA = [ 1 2 12 2 3 2 3 ]

Café Python

Voici un exemple de génération de matrice creuse aléatoire, et son affichage spécial:

Voici un exemple de conversion d'une matrice creuse en une matrice 'pleine' (dense):

Voici un exemple d'enregistrement d'une matrice creuse au format COO.