An improved recursive graph bipartitioning algorithm for well balanced domain decomposition
Résumé
In the context of hybrid sparse linear solvers based on domain decomposition and Schur complement approaches, getting a domain decomposition tool leading to a good balancing of both the internal node set size and the interface node set size for all the domains is a critical point for load balancing and efficiency issues in a parallel computation context. For this purpose, we revisit the original algorithm introduced by Lipton, Rose and Tarjan which performed the recursion for nested dissection in a particular manner. From this specific recursive strategy, we propose in this paper several variations of the existing algorithms in the multilevel Scotch partitioner that take into account these multiple criteria and we illustrate the improved results on a collection of graphs corresponding to finite element meshes used in numerical scientific applications.
Dans le cadre des solveurs linéaires creux hybrides basés sur l'approche de décomposition de domaines avec complément de Schur, la mise au point d'un outil de décomposition de domaines permettant d'obtenir à la fois un bon équilibrage des intérieurs et des interfaces pour tous les domaines est un point critique pour l'équilibrage de la charge et l'efficacité dans un cadre de calculs parallèles. Dans cet objectif, nous réexaminons l'algorithme orignal introduit par Lipton, Rose et Tarjan qui effectue la récursivité de la dissection emboîtée d'une manière particulière. En partant de cette stratégie récursive spécifique, nous proposons dans ce papier plusieurs variantes des algorithmes existants dans le partitionneur multi-niveaux \scotch qui prennent en considération ces multiples critères et nous illustrons l'amélioration de nos résultats sur une collection de graphes correspondants à des maillages d'éléments finis utilisés dans des applications numériques scientifiques.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...