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
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.
PaToH (Partitioning Tool for Hypergraphs)
In Encyclopedia of Parallel Computing,
2011.
A matrix partitioning interface to PaToH in MATLAB
Parallel Computing,
2010.
On Two-Dimensional Sparse Matrix Partitioning: Models, Methods, and a Recipe
SIAM Journal on Scientific Computing (SISC),
2010.
A Hypergraph-Partitioning Approach for Coarse-Grain Decomposition
In ACM/IEEE SC2001,
2001.
A Fine-Grain Hypergraph Model for 2D Decomposition of Sparse Matrices
In Proceedings of 15th International Parallel and Distributed Processing Symposium (IPDPS),
2001.
Hypergraph Models for Sparse Matrix Partitioning and Reordering
Ümit V. Çatalyürek
PhD thesis,
Bilkent University, Computer Engineering and Information Science ,
1999.
Hypergraph-Partitioning Based Decomposition for Parallel Sparse-Matrix Vector Multiplication
IEEE Transactions on Parallel and Distributed Systems,
1999.
PaToH: A Multilevel Hypergraph Partitioning Tool, Version 3.0
Bilkent University, Department of Computer Engineering ,
1999.
Decomposing linear programs for parallel solution
Lecture notes in Computer Science,
1996.
Decomposing irregularly sparse matrices for parallel matrix-vector multiplications
In Proceedings of 3rd International Symposium on Solving Irregularly Structured Problems in Parallel, Irregular’96,
1996.
A Hypergraph Model for Mapping Repeated Sparse Matrix-Vector Product Computations onto Multicomputers
In Proceedings of International Conference on High Performance Computing,
1995.