PT-Scotch

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 51 articles )

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

1 2 3 next

  1. Bollhöfer, Matthias; Schenk, Olaf; Janalik, Radim; Hamm, Steve; Gullapalli, Kiran: State-of-the-art sparse direct solvers (2020)
  2. Feppon, F.; Allaire, G.; Dapogny, C.; Jolivet, P.: Topology optimization of thermal fluid-structure systems using body-fitted meshes and parallel computing (2020)
  3. Grote, Marcus J.; Nataf, Frédéric; Tang, Jet Hoe; Tournier, Pierre-Henri: Parallel controllability methods for the Helmholtz equation (2020)
  4. Krasnopolsky, B.: Revisiting performance of biCGStab methods for solving systems with multiple right-hand sides (2020)
  5. Moxey, David; Amici, Roman; Kirby, Mike: Efficient matrix-free high-order finite element evaluation for simplicial elements (2020)
  6. 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)
  7. Jakob M. Maljaars, Chris N. Richardson, Nathan Sime: LEoPart: a particle library for FEniCS (2019) arXiv
  8. Mehrdoost, Zahra: Unstructured grid adaptation for multiscale finite volume method (2019)
  9. Agullo, Emmanuel; Darve, Eric; Giraud, Luc; Harness, Yuval: Low-rank factorizations in data sparse hierarchical algorithms for preconditioning symmetric positive definite matrices (2018)
  10. 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)
  11. Schornbaum, Florian; Rüde, Ulrich: Extreme-scale block-structured adaptive mesh refinement (2018)
  12. Badia, Santiago; Nguyen, Hieu: Relaxing the roles of corners in BDDC by perturbed formulation (2017)
  13. Benk, Janos; Denk, Georg; Waldherr, Konrad: A holistic fast and parallel approach for accurate transient simulations of analog circuits (2017)
  14. Burstedde, Carsten; Holke, Johannes: Coarse mesh partitioning for tree-based AMR (2017)
  15. Jacquelin, Mathias; Lin, Lin; Yang, Chao: \textttPselinv-- a distributed memory parallel algorithm for selected inversion, the symmetric case (2017)
  16. Pirova, Anna; Meyerov, Iosif; Kozinov, Evgeniy; Lebedev, Sergey: PMORSy: parallel sparse matrix ordering software for fill-in minimization (2017)
  17. Ponce, Colin; Vassilevski, Panayot S.: Solving graph Laplacian systems through recursive partitioning and two-grid preconditioning (2017)
  18. Badia, Santiago; Nguyen, Hieu: Balancing domain decomposition by constraints and perturbation (2016)
  19. Burstedde, Carsten; Holke, Johannes: A tetrahedral space-filling curve for nonconforming adaptive meshes (2016)
  20. Lee, J.; Cookson, A.; Roy, I.; Kerfoot, E.; Asner, L.; Vigueras, G.; Sochi, T.; Deparis, S.; Michler, C.; Smith, N. P.; Nordsletten, D. A.: Multiphysics computational modeling in (\mathcalC\mathbfHeart) (2016)

1 2 3 next