An improved recursive graph bipartitioning algorithm for well balanced domain decomposition

Astrid Casadei 1, 2 Pierre Ramet 1, 2 Jean Roman 1, 2
Résumé : 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.
Type de document :
Rapport
[Research Report] RR-8582, INRIA. 2014, pp.29
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01056749
Contributeur : Pierre Ramet <>
Soumis le : mercredi 20 août 2014 - 14:43:08
Dernière modification le : jeudi 11 janvier 2018 - 06:22:35
Document(s) archivé(s) le : jeudi 27 novembre 2014 - 12:01:04

Fichier

RR-8582.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01056749, version 1

Collections

Citation

Astrid Casadei, Pierre Ramet, Jean Roman. An improved recursive graph bipartitioning algorithm for well balanced domain decomposition. [Research Report] RR-8582, INRIA. 2014, pp.29. 〈hal-01056749〉

Partager

Métriques

Consultations de la notice

259

Téléchargements de fichiers

169