An improved recursive graph bipartitioning algorithm for well balanced domain decomposition

Astrid Casadei 1, 2 Pierre Ramet 1, 2 Jean Roman 1, 2
Abstract : 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.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01056749
Contributor : Pierre Ramet <>
Submitted on : Wednesday, August 20, 2014 - 2:43:08 PM
Last modification on : Thursday, January 11, 2018 - 6:22:35 AM
Long-term archiving on: Thursday, November 27, 2014 - 12:01:04 PM

File

RR-8582.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

304

Files downloads

258