Matrice creuse

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 ]

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 (en) 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 exhautif des solveurs disponibles qui prennent en compte les avantages des matrices sparses 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