Matrice creuse - Définition
La liste des auteurs de cet article est disponible ici.
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.
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.
Résolution d'équations représentées par une matrice creuse
Des méthodes itératives et directes existent 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é.
