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

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

1 2 next

  1. Badia, Santiago; Nguyen, Hieu: Balancing domain decomposition by constraints and perturbation (2016)
  2. Burstedde, Carsten; Holke, Johannes: A tetrahedral space-filling curve for nonconforming adaptive meshes (2016)
  3. 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\boldHeart$ (2016)
  4. Liu, Xiao; Xia, Jianlin; de Hoop, Maarten V.: Parallel randomized and matrix-free direct solvers for large structured dense linear systems (2016)
  5. Yakovlev, Sergey; Moxey, David; Kirby, Robert M.; Sherwin, Spencer J.: To CG or to HDG: a comparative study in 3D (2016)
  6. Delling, Daniel; Fleischman, Daniel; Goldberg, Andrew V.; Razenshteyn, Ilya; Werneck, Renato F.: An exact combinatorial algorithm for minimum graph bisection (2015)
  7. Gorobets, A.V.: Parallel technology for numerical modeling of fluid dynamics problems by high-accuracy algorithms (2015)
  8. Loneland, Atle; Marcinkowski, Leszek; Rahman, Talal: Edge-based Schwarz methods for the Crouzeix-Raviart finite volume element discretization of elliptic problems (2015)
  9. Naumov, M.; Arsaev, M.; Castonguay, P.; Cohen, J.; Demouth, J.; Eaton, J.; Layton, S.; Markovskiy, N.; Reguly, I.; Sakharnykh, N.; Sellappan, V.; Strzodka, R.: AmgX: a library for GPU accelerated algebraic multigrid and preconditioned iterative methods (2015)
  10. Röhrig-Zöllner, Melven; Thies, Jonas; Kreutzer, Moritz; Alvermann, Andreas; Pieper, Andreas; Basermann, Achim; Hager, Georg; Wellein, Gerhard; Fehske, Holger: Increasing the performance of the Jacobi-Davidson method by blocking (2015)
  11. Cardiff, P.; Karač, A.; Ivanković, A.: A large strain finite volume method for orthotropic bodies with general material orientations (2014)
  12. Spillane, N.; Dolean, V.; Hauret, P.; Nataf, F.; Pechstein, C.; Scheichl, R.: Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps (2014)
  13. Brandfass, B.; Alrutz, T.; Gerhold, T.: Rank reordering for MPI communication optimization (2013)
  14. Feldmann, Andreas Emil: Fast balanced partitioning is hard even on grids and trees (2013)
  15. Havé, Pascal; Masson, Roland; Nataf, Frédéric; Szydlarski, Mikolaj; Xiang, Hua; Zhao, Tao: Algebraic domain decomposition methods for highly heterogeneous problems (2013)
  16. Kuhlemann, Verena; Vassilevski, Panayot S.: Improving the communication pattern in matrix-vector operations for large scale-free graphs by disaggregation (2013)
  17. Šidlof, Petr; Horáček, Jaromír; Řidký, Václav: Parallel CFD simulation of flow in a 3D model of vibrating human vocal folds (2013)
  18. Wittmann, M.; Zeiser, T.; Hager, G.; Wellein, G.: Domain decomposition and locality optimization for large-scale lattice Boltzmann simulations (2013)
  19. Ducournau, Aurélien; Bretto, Alain; Rital, Soufiane; Laget, Bernard: A reductive approach to hypergraph clustering: an application to image segmentation (2012)
  20. Feldmann, Andreas Emil: Fast balanced partitioning is hard even on grids and trees (2012)

1 2 next