Etude du remplissage lors des factorisations des matrices creuses

Plusieurs problèmes dans les simulations numériques aboutissent à la résolution du système linéaire creux Ax = b.

L'obtention de la solution x de ce système par une méthode directe passe souvent par plusieurs étapes.

Entre autre la renumérotation, la factorisation symbolique, la factorisation numérique et la résolution.

Notre travail porte sur l'étude du remplissage et des méthodes de minimisation de ce remplissage produit lors de la factorisation (LU ou QR) de la matrice A.

Notre contribution se situe au niveau de l'implémentation de la méthode des dissections emboitées.

La dissection emboitée étant une heuristique de minimisation du remplissage qui permet d'effectuer une bissection récursive du graphe de la matrice.

Cette implémentation a été faite en utilisant Metis pour avoir un programme Matlab.

Des tests ont été faits sur des matrices téléchargées sur la collection des matrices Tim Davis Matrix Collection.

Ces tests nous ont permis entre autres de comparer les remplissages obtenus lors des factorisations de la matrice A par les méthodes du degré minimum, de Mc-Cuthill inverse et des dissections emboitées.