Matrice creuse

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