PT-Scotch: A tool for efficient parallel graph ordering

By C. Chevalier, F. Pellegrini. Parallel Computing, 2008

440 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/f272a103909ecabbbe13b1463e2dfd5c32f0552b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Qinya Liu
2. Jeroen Tromp
3. Marie E. Rognes
4. Garth N. Wells
5. Anders Logg

In Computer Networks and Communications

1. Dimitri Komatitsch
2. Marie E. Rognes
3. Garth N. Wells
4. Anders Logg
5. Prabal Singh Verma

In Electrical and Electronic Engineering

1. Qinya Liu
2. Dimitri Komatitsch
3. Roland Martin
4. Jeroen Tromp
5. Marie E. Rognes
6. T. Nissen‐Meyer
7. Yang Luo
8. Garth N. Wells

Citations in the corpus

• The JOREK non-linear extended MHD code and applications to large-scale instabilities and their control in magnetically confined fusion plasmas (2020, methodology): “PT-Scotch [135] or ParMETIS [136] are used internally by the solvers, to minimize fill-in during the matrix factorization and to achieve good performance.”
• Forward and adjoint simulations of seismic wave propagation on fully unstructured hexahedral meshes (2011, methodology): “To do so, we make use of an external partitioner, namely SCOTCH (Pellegrini & Roman 1996; Chevalier & Pellegrini 2008), which we use to balance spectralelement computations on an arbitrary number of cores.”
• The FEniCS Project Version 1.5 (2015, methodology): “…sparse LU and Cholesky decomposition [Hénon et al., 2002] • Trilinos ≥ 11.0.0; provides mesh partitioning and coloring [Heroux et al., 2005] • SCOTCH; provides mesh partitioning and DOF reordering [Chevalier and Pellegrini, 2006] • ParMETIS ≥ 4.0.2; provides mesh partitioning [Karypis and…”