Matrice clairsemée

Matrice clairsemée

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.

Sommaire

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 ai, 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 aij 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 aij 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 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, no 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, no 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 des mathématiques
Ce document provient de « Matrice creuse ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Matrice clairsemée de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Allende (météorite) — Météorite d Allende Fragment d Allende Caractéristiques Type Chondrite Classe Chondrite carbonée …   Wikipédia en Français

  • Reconstruction 3D à partir d'images — La reconstruction 3D à partir d images, image based 3D reconstruction en anglais, désigne la technique qui permet d obtenir une représentation en trois dimensions d un objet ou d une scène à partir d un ensemble d images prises sous différents… …   Wikipédia en Français

  • MORPHOGÉNIQUES (SYSTÈMES) — Les géographes appellent «système morphogénique» (ou système d’érosion) toute combinaison complexe de processus qui élabore le relief de vastes portions de continent correspondant à des ensembles morphostructuraux ou bioclimatiques. Selon les… …   Encyclopédie Universelle

  • Corine Land Cover — est une base de données européenne d’occupation biophysique des sols. Ce projet est piloté par l Agence européenne de l environnement[1] et couvre 38 Etats. La partie française est réalisée par le Service de l Observation et des Statistiques[2]… …   Wikipédia en Français

  • Tourreilles — 43° 01′ 23″ N 2° 10′ 16″ E / 43.0230555556, 2.17111111111 …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”