Skip to Main content Skip to Navigation

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 metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Pierre Ramet Connect in order to contact the contributor
Submitted on : Wednesday, August 20, 2014 - 2:43:08 PM
Last modification on : Saturday, December 4, 2021 - 3:06:10 AM
Long-term archiving on: : Thursday, November 27, 2014 - 12:01:04 PM


Files produced by the author(s)


  • HAL Id : hal-01056749, version 1



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⟩



Record views


Files downloads