Matrice creuse
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
Une matrice creuse (sparse matrix en anglais) est une matrice contenant beaucoup de zéros.
Certains domaines utilisent des matrices creuses de grande taille. La proportion élevée de zéros est une forme de redondance, qui permet d'optimiser les calculs et le stockage.
Les matrices creuses sont couramment utilisées lorsque l'on s'intéresse à la résolution d'un problème de type éléments finis.
La structure de données naïve pour une matrice A est un tableau bi-dimensionnel. Chaque case du tableau représente un élément Ai,j de la matrice et est accessible par deux indices i et j. Pour une matrice de n×m on a besoin de (n*m) / 8 octets pour représenter la matrice si l'on suppose qu'une « case » de la matrice est codée par 1 bit.
Autrement, une matrice creuse peut trouver une représentation efficace à l'aide d'une liste bilinéaire, où l'on fait le choix de ne pas représenter en mémoire les éléments nuls. L'élément initial est divisé en plusieurs champs: nombre de lignes, nombre de colonnes, pointeur vers les lignes, pointeur vers les colonnes, etc. Cette "tête de liste" pointe vers une liste de ligne pointant vers la tête de liste contenant les éléments de des lignes ayant des éléments non nuls. De même, la liste de colonnes contient les indices et les têtes de listes des colonnes ayant des éléments non nuls. Ceci permet un gain considérable de mémoire dans le cas où les matrices sont très grandes mais contiennent peu d'éléments significatifs, bien que coûtant le parcours des listes pour l'accès à un élément spécifique.
