Matrice creuse

Une matrice creuse obtenue lors de la résolution d'un problème éléments finis. Les éléments non-nuls sont représentés en noir.

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ées à 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ée 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 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 structure de données qui prennent en compte la structure peu dense de la matrice. Les opérations utilisant les structures et les algorithmes de base sur les matrices sont lents et utilisent une grande quantité de mémoire quand ils sont utilisés sur de grandes matrices creuses. Ces données sont facilement compressibles, et cette compression amène presque à chaque fois une baisse significative de la consommation mémoire. De plus, certaines matrices creuses de très grande taille ne sont pas manipulables par les algorithmes classiques.

Stockage des matrices creuses

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.

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 m + 1 (le nombre de lignes plus un). L'élément i de IA contient l'index dans le tableau A de la première entrée non nulle de la ligne i de la matrice M. La ligne i de la matrice originale est composée des éléments de A depuis l'index IA(i) jusqu'à l'index IA(i+1)-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 3×4 suivante

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

est représentée dans ce format par

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

Exemple

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.

Matrices diagonales

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.

Largeur de bande

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 largeur 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 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.

Phénomène de remplissage

Le remplissage (ou fill-in en anglais) d'une matrice creuse représente le nombre 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 permuttant 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éro 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.

Résolution d'équations représentées par une matrice creuse

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é.

Sources

• Page anglaise
• Tewarson, Reginald P, Sparse Matrices (Part of the Mathematics in Science & Engineering series), Academic Press Inc., May 1973. (This book, by a professor at the State University of New York at Stony Book, was the first book exclusively dedicated to Sparse Matrices. Graduate courses using this as a textbook were offered at that University in the early 1980s).
• Sparse Matrix Multiplication Package, Randolph E. Bank, Craig C. Douglas [1]
• Pissanetzky, Sergio 1984, "Sparse Matrix Technology", Academic Press
• R. A. Snay. Reducing the profile of sparse symmetric matrices. Bulletin Géodésique, 50:341–352, 1976. Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.

Liens externes

• (en)Norman E. Gibbs, William G. Poole, Jr. and Paul K. Stockmeyer, « A comparison of several bandwidth and profile reduction algorithms », dans ACM Transactions on Mathematical Software, vol. 2, n^o 4, 1976, p. 322–330 [texte intégral, lien DOI] 
• (en)John R. Gilbert, Cleve Moler and Robert Schreiber, « Sparse matrices in MATLAB: Design and Implementation », dans SIAM Journal on Matrix Analysis and Applications, vol. 13, n^o 1, 1992, p. 333–356 [texte intégral, lien DOI] 
• (en)Sparse Matrix Algorithms Research at the University of Florida, containing the UF sparse matrix collection.

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