Matrice creuse

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Dans la discipline de l'analyse numérique des mathématiques, une matrice creuse est une matrice contenant beaucoup de zéros.

Conceptuellement, les matrices creuses correspondent aux systèmes qui sont peu couplés. Si on considère une ligne de balles dont chacune est reliée à ses voisines directes par des élastiques, ce système serait représenté par une matrice creuse. Au contraire, si chaque balle de la ligne est reliée à toutes les autres balles, ce système serait représenté par une matrice dense. Ce concept de matrice creuse est très utilisé en analyse combinatoire et ses domaines d'applications tels que la théorie des réseaux, qui ont une faible densité de connexions.

Des matrices creuses de taille importante apparaissent souvent en science ou en ingénierie pour la résolution des équations aux dérivées partielles.

Quand on veut manipuler ou stocker des matrices creuses à l'aide de l'outil informatique, il est avantageux voire souvent nécessaire d'utiliser des algorithmes et des structures de données qui prennent en compte la structure peu dense de la matrice : dès lors que des coordonnées de ligne et de colonne donnent accès à une adresse, peu importe l'organisation physique des données.

Représenter physiquement tous ces zéros en mémoire quand ils sont utilisés sur de grandes matrices creuses serait coûteux et lent. Il est plus économique et plus rapide de dire que toute valeur non renseignée pour des coordonnées données est zéro. Cette compression de données amène presque toujours à une division importante de la consommation de mémoire, pour un surcoût négligeable de traitement. Certaines matrices creuses de très grande taille ne sont toutefois pas manipulables par les algorithmes classiques.

La structure de données naïve utilisée pour stocker une matrice est un tableau bidimensionnel. Chaque entrée du tableau représente un élément a_{i, j} de la matrice qui peut être atteint par les deux indices i et j. Pour une matrice m×n il faut au moins (m×n) espaces mémoire de taille fixe pour représenter la matrice.

Beaucoup, si ce n'est la majorité des entrées d'une matrice creuse, sont des zéros. L'idée de base est alors de ne stocker que les entrées non nulles de la matrice, plutôt que d'en stocker l'intégralité. En fonction du nombre et de la répartition des entrées non nulles, des structures de données différentes peuvent être utilisées et amènent de grandes économies dans la taille utilisée en mémoire par rapport à la structure naïve. Cette technique est aussi utilisée lorsque la matrice représente un graphe : s'il y a peu d'arêtes, on préfère la liste d'adjacence à la matrice d'adjacence.

Un exemple d'une telle représentation est le format Yale Sparse Matrix. 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.

• Le premier tableau est noté A et est de longueur NNN. Il contient toutes les valeurs des entrées non nulles de M de gauche à droite et de haut en bas (les valeurs sont prises de gauche à droite sur la première ligne, puis de gauche à droite sur la deuxième et ainsi de suite).
• Le deuxième tableau est noté IA de longueur ${\displaystyle m+1}$ (le nombre de lignes plus un). Il est défini de façon récursive : IA(0)=0 et IA(i+1)=IA(i)+NNNi où NNNi est le nombre d'entrées non nulles de la ligne i (en indexant à partir de 0). La ligne i de la matrice originale M est composée des éléments de A depuis l'index IA(i) jusqu'à l'index IA(i+1)-1 (ou bien elle est vide si IA(i)=IA(i+1)).
• Le troisième tableau est noté JA de longueur NNN contient le numéro de la colonne de chaque élément de A.

Par exemple, la matrice 4×8 suivante

[ 1 2 0 0 0 0 0 0 ]
[ 0 3 0 0 0 0 9 0 ]
[ 0 0 0 0 0 0 0 0 ]
[ 0 0 1 0 0 0 0 4 ]

est représentée dans ce format par

A  = [ 1 2 3 9 1 4 ]
IA = [ 0 2 4 4 6 ]
JA = [ 0 1 1 6 2 7 ]

Un bitmap qui n'a que deux couleurs, dont une dominante (par exemple un fichier contenant une signature), peut être sauvegardé sous la forme d'une matrice creuse ne contenant que les pixels de la couleur non dominante.

Une structure très efficace pour stocker une matrice diagonale est de ne stocker que les entrées de la diagonale principale dans un tableau à une dimension. Une matrice diagonale n×n ne nécessite que n entrées.

La largeur de bande basse d'une matrice M est le plus petit entier p tel que les entrées a_ij sont nulles pour i > j + p. De même, la largeur de bande haute est le plus petit entier p tel que les entrées a_ij sont nulles pour i < j - p. Par exemple une matrice tridiagonale à une largeur de bande basse de 1 et une largeur de bande haute de 1.

Les matrices avec de petites largeurs de bande haute et basse sont nommées des matrices bande et des algorithmes plus efficaces que ceux sur les matrices creuses existent souvent.

Par exemple l'algorithme de Cuthill-McKee (en) permet de réduire la largeur de bande d'une matrice creuse et symétrique, et de nombreuses autres méthodes existent pour réduire cette largeur de bande.

Le remplissage (ou fill-in en anglais) d'une matrice creuse représente le nombre d'entrées qui, pendant l'exécution d'un algorithme, passent d'une valeur nulle à une valeur différente de zéro. Pour réduire les besoins supplémentaires en mémoire et en coût de calcul que ce phénomène induit, il est nécessaire de limiter ce remplissage, ce qui peut être effectué en permutant colonnes et lignes de la matrice. Le remplissage est une notion théorique qui ne change pas entre les différents algorithmes (factorisation de Cholesky, décomposition QR…) qui peuvent être appliqués sur la matrice, mais le nombre de zéros qui prennent effectivement une valeur non nulle pendant l'exécution varie selon l'algorithme appliqué, et quelques algorithmes possèdent une version symbolique qui permet d'obtenir le remplissage dans le pire des cas, tel que la décomposition symbolique de Cholesky (en).

Des méthodes itératives et directes existent pour résoudre des systèmes représentés par des matrices creuses. Une méthode itérative très utilisée est la méthode du gradient conjugué.

Ci-dessous se trouve un tableau non exhaustif des solveurs disponibles qui prennent en compte les avantages des matrices éparses et permettent de résoudre un système linéaire de type Ax=b:

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sparse matrix » (voir la liste des auteurs).
• (en) Reginald P. Tewarson, Sparse Matrices (Part of the Mathematics in Science & Engineering series), Academic Press, 1973.
• (en) Randolph E. Bank et Craig C. Douglas, Sparse Matrix Multiplication Package.
• (en) Sergio Pissanetzky, Sparse Matrix Technology, Academic Press, 1984.
• (en) R. A. Snay, « Reducing the profile of sparse symmetric matrices », dans Bulletin Géodésique, 50:341–352, 1976. Aussi dans NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.

• (en) Norman E. Gibbs, William G. Poole, Jr. and Paul K. Stockmeyer, « A comparison of several bandwidth and profile reduction algorithms », ACM Transactions on Mathematical Software, vol. 2, n^o 4,‎ 1976, p. 322-330 (DOI 10.1145/355705.355707, lire en ligne)
• (en) John R. Gilbert, Cleve Moler and Robert Schreiber, « Sparse matrices in MATLAB: Design and Implementation », SIAM Journal on Matrix Analysis and Applications, vol. 13, n^o 1,‎ 1992, p. 333-356 (DOI 10.1137/0613024, lire en ligne)
• (en) Sparse Matrix Algorithms Research à l'université de Floride
• (en) R.Buda, « Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm », dans Computational Economics, 31(4), 2008, p. 397-408

• Portail des mathématiques
• Portail de l’informatique