Parallel partitioning with Zoltan: is hypergraph partitioning worth it? Graph partitioning is an important and well studied problem in combinatorial scientific computing, and is commonly used to reduce communication in parallel computing. Different models (graph, hypergraph) and objectives (edge cut, boundary vertices) have been proposed. Hypergraph partitioning has become increasingly popular over the last decade. Its main strength is that it accurately captures communication volume, but it is slower to compute than graph partitioning. par We present an empirical study of the Zoltan parallel hypergraph and graph (PHG) partitioner on graphs from the 10th DIMACS implementation challenge and some directed (nonsymmetric) graphs. We show that hypergraph partitioning is superior to graph partitioning on directed graphs (nonsymmetric matrices), where the communication volume is reduced in several cases by over an order of magnitude, but has no significant benefit on undirected graphs (symmetric matrices) using current parallel software tools.

References in zbMATH (referenced in 62 articles , 1 standard article )

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

1 2 3 4 next

  1. Gnanasekaran, Abeynaya; Darve, Eric: Hierarchical orthogonal factorization: sparse square matrices (2022)
  2. Torun, Tugba; Torun, F. Sukru; Manguoglu, Murat; Aykanat, Cevdet: Partitioning and reordering for spike-based distributed-memory parallel Gauss-Seidel (2022)
  3. Ziganurova, L.; Shchur, L.: Algorithm for adaptive mesh redistribution in lattice Boltzmann simulations (2022)
  4. Henneking, S.; Demkowicz, L.: A numerical study of the pollution error and DPG adaptivity for long waveguide simulations (2021)
  5. Holke, Johannes; Knapp, David; Burstedde, Carsten: An optimized, parallel computation of the ghost layer for adaptive hybrid forest meshes (2021)
  6. Ramachandran, Prabhu; Bhosale, Aditya; Puri, Kunal; Negi, Pawan; Muta, Abhinav; Dinesh, A.; Menon, Dileep; Govind, Rahul; Sanka, Suraj; Sebastian, Amal S.; Sen, Ananyo; Kaushik, Rohan; Kumar, Anshuman; Kurapati, Vikas; Patil, Mrinalgouda; Tavker, Deep; Pandey, Pankaj; Kaushik, Chandrashekhar; Dutt, Arkopal; Agarwal, Arpit: PySPH: a Python-based framework for smoothed particle hydrodynamics (2021)
  7. Rasmussen, Atgeirr Flø; Sandve, Tor Harald; Bao, Kai; Lauser, Andreas; Hove, Joakim; Skaflestad, Bård; Klöfkorn, Robert; Blatt, Markus; Rustad, Alf Birger; Sævareid, Ove; Lie, Knut-Andreas; Thune, Andreas: The open porous media flow reservoir simulator (2021)
  8. Saxena, Gaurav; Ponce-de-Leon, Miguel; Montagud, Arnau; Vicente Dorca, David; Valencia, Alfonso: BioFVM-X: an MPI+OpenMP 3-D simulator for biological systems (2021)
  9. Thune, Andreas; Cai, Xing; Rustad, Alf Birger: On the impact of heterogeneity-aware mesh partitioning and non-contributing computation removal on parallel reservoir simulations (2021)
  10. Davis, Timothy A.; Hager, William W.; Kolodziej, Scott P.; Yeralan, S. Nuri: Algorithm 1003: Mongoose, a graph coarsening and partitioning library (2020)
  11. 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)
  12. David Zwick: ppiclF: A Parallel Particle-In-Cell Library in Fortran (2019) not zbMATH
  13. Gottesbüren, Lars; Hamann, Michael; Wagner, Dorothea: Evaluation of a flow-based hypergraph bipartitioning algorithm (2019)
  14. Li, Shu-Jie: Mesh curving and refinement based on cubic Bézier surface for high-order discontinuous Galerkin methods (2019)
  15. Roberts, Nathan V.: Camellia: a rapid development framework for finite element solvers (2019)
  16. Shaydulin, Ruslan; Chen, Jie; Safro, Ilya: Relaxation-based coarsening for multilevel hypergraph partitioning (2019)
  17. 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)
  18. D’Elia, M.; Edwards, H. C.; Hu, J.; Phipps, E.; Rajamanickam, S.: Ensemble grouping strategies for embedded stochastic collocation methods applied to anisotropic diffusion problems (2018)
  19. Heuer, Tobias; Sanders, Peter; Schlag, Sebastian: Network flow-based refinement for multilevel hypergraph partitioning (2018)
  20. Shaydulin, Ruslan; Safro, Ilya: Aggregative coarsening for multilevel hypergraph partitioning (2018)

1 2 3 4 next

Further publications can be found at: http://www.cs.sandia.gov/zoltan/Zoltan_pubs.html