Hypergraphs

Computational Hypergraph Models for Load Balancing and Sparse Matrix Partitioning and Ordering

During my PhD studies in late 90s, we have introduced computational hypergraph models for modeling applications with irregular data dependencies. After that, hypergraph-based models gained wide acceptance in the parallel computing community for modeling various problems. In simple terms, hypergraphs are generalization of graphs where each edge (hyperedge) can connect more than two vertices. With that, hypergraphs provides a natural way to represent multi-way interactions, and hence enables elegant modeling of various communication metrics.

Column-net hypergraph representation of a toy sparse matrix and its row-wise partitioning (with reordering) via hypergraph partitioning.

The prototypical application for irregular computational dependencies is Sparse-Matrix Vector Multiplication (SpMV). We have proposed new models and methods for modeling different 1D and 2D data and work partitioning problems. The figure below illustrates a taxonomy for sparse matrix partitioning models and methods.

A taxonomy for sparse matrix partitioning models and methods. There are three basic hypergraph models. Different partitioning methods use these models.

Related Publications

  1. JRNL
    More Recent Advances in (Hyper)Graph Partitioning
    Ümit V. Çatalyürek, Karen D. Devine, Marcelo Fonseca Faraj, Lars Gottesbüren, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier, and Dorothea Wagner
    ACM Computing Surveys, 2023.
  2. Chap
    PaToH (Partitioning Tool for Hypergraphs)
    Ümit V. Çatalyürek, and Cevdet Aykanat
    In Encyclopedia of Parallel Computing, 2011.
  3. JRNL
    A matrix partitioning interface to PaToH in MATLAB
    Bora Uçar, Ümit V. Çatalyürek, and Cevdet Aykanat
    Parallel Computing, 2010.
  4. JRNL
    On Two-Dimensional Sparse Matrix Partitioning: Models, Methods, and a Recipe
    Ümit V. Çatalyürek, Cevdet Aykanat, and Bora Uçar
    SIAM Journal on Scientific Computing (SISC), 2010.
  5. Conf
    A Hypergraph-Partitioning Approach for Coarse-Grain Decomposition
    Ümit V. Çatalyürek, and Cevdet Aykanat
    In ACM/IEEE SC2001, 2001.
  6. Conf
    A Fine-Grain Hypergraph Model for 2D Decomposition of Sparse Matrices
    Ümit V. Çatalyürek, and Cevdet Aykanat
    In Proceedings of 15th International Parallel and Distributed Processing Symposium (IPDPS), 2001.
  7. PhD
    Hypergraph Models for Sparse Matrix Partitioning and Reordering
    Ümit V. Çatalyürek
    PhD thesis, Bilkent University, Computer Engineering and Information Science , 1999.
  8. JRNL
    Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication
    Ümit V. Çatalyürek, and Cevdet Aykanat
    IEEE Transactions on Parallel and Distributed Systems, 1999.
  9. Tech
    PaToH: A Multilevel Hypergraph Partitioning Tool, Version 3.0
    Ümit V. Çatalyürek, and Cevdet Aykanat
    Bilkent University, Department of Computer Engineering , 1999.
  10. JRNL
    Decomposing linear programs for parallel solution
    Ali Pınar, Ümit V. Çatalyürek, Cevdet Aykanat, and M. Pınar
    Lecture notes in Computer Science, 1996.
  11. Conf
    Decomposing irregularly sparse matrices for parallel matrix-vector multiplications
    Ümit V. Çatalyürek, and Cevdet Aykanat
    In Proceedings of 3rd International Symposium on Solving Irregularly Structured Problems in Parallel, Irregular’96, 1996.
  12. Conf
    A Hypergraph Model for Mapping Repeated Sparse Matrix-Vector Product Computations onto Multicomputers
    Ümit V. Çatalyürek, and Cevdet Aykanat
    In Proceedings of International Conference on High Performance Computing, 1995.