Séminaire ACSIOM :

Le 31 janvier 2012 à 11:00 - salle 431

Présentée par Laverne Thomas - Schlumberger, Montpellier

Graphes et résolution des systèmes linéaires éléments finis

La théorie des graphes joue un rôle fondamental dans l'analyse des propriétés algorithmiques des solveurs linéaires. L'étude de l'ordre d'élimination dans les méthodes directes en est un exemple bien connu. Quand la matrice est associée à un Laplacien (ou plus généralement à un problème éléments finis) il est possible de tirer parti de certaines propriétés du graphe sous-jacent. Nous montrerons comment l'ont peut obtenir des conditions théoriques sur la complexité de la méthode de résolution du système linéaire. A partir de cette analyse, nous indiquerons comment construire un algorithme performant en pratique. Outline : - Graphe et laplacien, problèmes éléments finis - Élimination directe - Conductance - Arbre de Recouvrement Maximal - Extension de la méthode