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

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

1 2 next

  1. Burstedde, Carsten; Holke, Johannes: A tetrahedral space-filling curve for nonconforming adaptive meshes (2016)
  2. 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)
  3. Yakovlev, Sergey; Moxey, David; Kirby, Robert M.; Sherwin, Spencer J.: To CG or to HDG: a comparative study in 3D (2016)
  4. Delling, Daniel; Fleischman, Daniel; Goldberg, Andrew V.; Razenshteyn, Ilya; Werneck, Renato F.: An exact combinatorial algorithm for minimum graph bisection (2015)
  5. Gorobets, A.V.: Parallel technology for numerical modeling of fluid dynamics problems by high-accuracy algorithms (2015)
  6. Loneland, Atle; Marcinkowski, Leszek; Rahman, Talal: Edge-based Schwarz methods for the Crouzeix-Raviart finite volume element discretization of elliptic problems (2015)
  7. 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)
  8. 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)
  9. Cardiff, P.; Karač, A.; Ivanković, A.: A large strain finite volume method for orthotropic bodies with general material orientations (2014)
  10. 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)
  11. Brandfass, B.; Alrutz, T.; Gerhold, T.: Rank reordering for MPI communication optimization (2013)
  12. Feldmann, Andreas Emil: Fast balanced partitioning is hard even on grids and trees (2013)
  13. Havé, Pascal; Masson, Roland; Nataf, Frédéric; Szydlarski, Mikolaj; Xiang, Hua; Zhao, Tao: Algebraic domain decomposition methods for highly heterogeneous problems (2013)
  14. Kuhlemann, Verena; Vassilevski, Panayot S.: Improving the communication pattern in matrix-vector operations for large scale-free graphs by disaggregation (2013)
  15. Šidlof, Petr; Horáček, Jaromír; Řidký, Václav: Parallel CFD simulation of flow in a 3D model of vibrating human vocal folds (2013)
  16. Wittmann, M.; Zeiser, T.; Hager, G.; Wellein, G.: Domain decomposition and locality optimization for large-scale lattice Boltzmann simulations (2013)
  17. Ducournau, Aurélien; Bretto, Alain; Rital, Soufiane; Laget, Bernard: A reductive approach to hypergraph clustering: an application to image segmentation (2012)
  18. Feldmann, Andreas Emil: Fast balanced partitioning is hard even on grids and trees (2012)
  19. Gharti, Hom Nath; Komatitsch, Dimitri; Oye, Volker; Martin, Roland; Tromp, Jeroen: Application of an elastoplastic spectral element method to 3D slope stability analysis (2012)
  20. Jolivet, P.; Dolean, V.; Hecht, F.; Nataf, F.; Prud’Homme, C.; Spillane, N.: High performance domain decomposition methods on massively parallel architectures with freefem++ (2012)

1 2 next