Matrice creuse - Définition

Introduction

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.