Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Matrice creuse
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.