PT-Scotch: A tool for efficient parallel graph ordering. The parallel ordering of large graphs is a difficult problem, because on the one hand minimum degree algorithms do not parallelize well, and on the other hand the obtainment of high quality orderings with the nested dissection algorithm requires efficient graph bipartitioning heuristics, the best sequential implementations of which are also hard to parallelize. This paper presents a set of algorithms, implemented in the PT-Scotch software package, which allows one to order large graphs in parallel, yielding orderings the quality of which is only slightly worse than the one of state-of-the-art sequential algorithms. Our implementation uses the classical nested dissection approach but relies on several novel features to solve the parallel graph bipartitioning problem. Thanks to these improvements, PT-Scotch produces consistently better orderings than ParMeTiS on large numbers of processors.

References in zbMATH (referenced in 61 articles )

Showing results 1 to 20 of 61.
Sorted by year (citations)

1 2 3 4 next

  1. Aldbaissy, Rim; Hecht, Frédéric; Mansour, Gihane; Sayah, Toni; Henri Tournier, Pierre: Scalable domain decomposition preconditioner for Navier-Stokes equations coupled with the heat equation (2022)
  2. Al Daas, Hussam; Grigori, Laura; Jolivet, Pierre; Tournier, Pierre-Henri: A multilevel Schwarz preconditioner based on a hierarchy of robust coarse spaces (2021)
  3. Hapla, Vaclav; Knepley, Matthew G.; Afanasiev, Michael; Boehm, Christian; van Driel, Martin; Krischer, Lion; Fichtner, Andreas: Fully parallel mesh I/O using PETSc DMPlex with an application to waveform modeling (2021)
  4. Holke, Johannes; Knapp, David; Burstedde, Carsten: An optimized, parallel computation of the ghost layer for adaptive hybrid forest meshes (2021)
  5. Zimmerman, Alexander G.; Kowalski, Julia: Mixed finite elements for convection-coupled phase-change in enthalpy form: open software verified and applied to 2D benchmarks (2021)
  6. Alberto Paganini, Florian Wechsung: Fireshape: a shape optimization toolbox for Firedrake (2020) arXiv
  7. Bollhöfer, Matthias; Schenk, Olaf; Janalik, Radim; Hamm, Steve; Gullapalli, Kiran: State-of-the-art sparse direct solvers (2020)
  8. Feppon, F.; Allaire, G.; Dapogny, C.; Jolivet, P.: Topology optimization of thermal fluid-structure systems using body-fitted meshes and parallel computing (2020)
  9. Fournier, Yvan: Massively parallel location and exchange tools for unstructured meshes (2020)
  10. Grote, Marcus J.; Nataf, Frédéric; Tang, Jet Hoe; Tournier, Pierre-Henri: Parallel controllability methods for the Helmholtz equation (2020)
  11. Kong, Fande; Wang, Yaqi; Gaston, Derek R.; Permann, Cody J.; Slaughter, Andrew E.; Lindsay, Alexander D.; DeHart, Mark D.; Martineau, Richard C.: A highly parallel multilevel Newton-Krylov-Schwarz method with subspace-based coarsening and partition-based balancing for the multigroup neutron transport equation on three-dimensional unstructured meshes (2020)
  12. Krasnopolsky, B.: Revisiting performance of biCGStab methods for solving systems with multiple right-hand sides (2020)
  13. Moxey, David; Amici, Roman; Kirby, Mike: Efficient matrix-free high-order finite element evaluation for simplicial elements (2020)
  14. Sander, Oliver: DUNE -- the distributed and unified numerics environment (2020)
  15. Chen, Chao; Cambier, Leopold; Boman, Erik G.; Rajamanickam, Sivasankaran; Tuminaro, Raymond S.; Darve, Eric: A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling (2019)
  16. Haddad, Mireille; Hecht, Frédéric; Sayah, Toni; Tournier, Pierre Henri: Parallel computing investigations for the projection method applied to the interface transport scheme of a two-phase flow by the method of characteristics (2019)
  17. Jakob M. Maljaars, Chris N. Richardson, Nathan Sime: LEoPart: a particle library for FEniCS (2019) arXiv
  18. Mehrdoost, Zahra: Unstructured grid adaptation for multiscale finite volume method (2019)
  19. Agullo, Emmanuel; Darve, Eric; Giraud, Luc; Harness, Yuval: Low-rank factorizations in data sparse hierarchical algorithms for preconditioning symmetric positive definite matrices (2018)
  20. Borrell, R.; Cajas, J. C.; Mira, D.; Taha, A.; Koric, S.; Vázquez, M.; Houzeaux, G.: Parallel mesh partitioning based on space filling curves (2018)

1 2 3 4 next