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 47 articles , 1 standard article )

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

1 2 3 next

  1. David Zwick: ppiclF: A Parallel Particle-In-Cell Library in Fortran (2019) not zbMATH
  2. Roberts, Nathan V.: Camellia: a rapid development framework for finite element solvers (2019)
  3. Shaydulin, Ruslan; Chen, Jie; Safro, Ilya: Relaxation-based coarsening for multilevel hypergraph partitioning (2019)
  4. 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)
  5. 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)
  6. Smith, Cameron W.; Rasquin, Michel; Ibanez, Dan; Jansen, Kenneth E.; Shephard, Mark S.: Improving unstructured mesh partitions for multiple criteria using mesh adjacencies (2018)
  7. Sushnikova, Daria A.; Oseledets, Ivan V.: “Compress and eliminate” solver for symmetric positive definite sparse matrices (2018)
  8. Burstedde, Carsten; Holke, Johannes: Coarse mesh partitioning for tree-based AMR (2017)
  9. Ibanez, Daniel A.; Seol, E. Seegyoung; Smith, Cameron W.; Shephard, Mark S.: PUMI: parallel unstructured mesh infrastructure (2016)
  10. 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)
  11. Louis, Anand; Makarychev, Yury: Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion (2016)
  12. Marras, Simone; Kelly, James F.; Moragues, Margarida; Müller, Andreas; Kopera, Michal A.; Vázquez, Mariano; Giraldo, Francis X.; Houzeaux, Guillaume; Jorba, Oriol: A review of element-based Galerkin methods for numerical weather prediction: finite elements, spectral elements, and discontinuous Galerkin (2016)
  13. Isaac, Tobin; Burstedde, Carsten; Wilcox, Lucas C.; Ghattas, Omar: Recursive algorithms for distributed forests of octrees (2015)
  14. Nejadmalayeri, Alireza; Vezolainen, Alexei; Brown-Dymkoski, Eric; Vasilyev, Oleg V.: Parallel adaptive wavelet collocation method for PDEs (2015)
  15. Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Christian Schulz: k-way Hypergraph Partitioning via n-Level Recursive Bisection (2015) arXiv
  16. Trask, Nathaniel; Maxey, Martin; Kim, Kyungjoo; Perego, Mauro; Parks, Michael L.; Yang, Kai; Xu, Jinchao: A scalable consistent second-order SPH solver for unsteady low Reynolds number flows (2015)
  17. Wang, Kun; Liu, Hui; Chen, Zhangxin: A scalable parallel black oil simulator on distributed memory parallel computers (2015)
  18. Ballard, G.; Carson, E.; Demmel, J.; Hoemmen, M.; Knight, N.; Schwartz, O.: Communication lower bounds and optimal algorithms for numerical linear algebra (2014)
  19. Fagginger Auer, B. O.; Bisseling, R. H.: Efficient matching for column intersection graphs (2014)
  20. Brandfass, B.; Alrutz, T.; Gerhold, T.: Rank reordering for MPI communication optimization (2013) ioport

1 2 3 next

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