Hypergraph partitioning

A hypergraph consists of vertices and hyperedges. A hyperedge connects one or more vertices. A graph can be cast as a hypergraph in one of two ways: either every pair of neighboring vertices form a hyperedge, or a vertex and all its neighbors form a hyperedge. The hypergraph model is well suited to parallel computing, where vertices correspond to data objects and hyperedges represent the communication requirements. The basic partitioning problem is to partition the vertices into k approximately equal sets such that the number of cut hyperedges is minimized. Most partitioners (including Zoltan-PHG) allows a more general model where both vertices and hyperedges can be assigned weights. It has been shown that the hypergraph model gives a more accurate representation of communication cost (volume) than the graph model. In particular, for sparse matrix-vector multiplication, the hypergraph model exactly represents communication volume. Sparse matrices can be partitioned either along rows or columns; in the row-net model the columns are vertices and each row corresponds to an hyperedge, while in the column-net model the roles of vertices and hyperedges are reversed.

Zoltan contains a native parallel hypergraph partitioner, called PHG (Parallel HyperGraph partitioner). In addition, Zoltan provides access to PaToH, a serial hypergraph partitioner. Note that PaToH is not part of Zoltan and should be obtained separately from the PaToH web site. Zoltan-PHG is a fully parallel multilevel hypergraph partitioner. For further technical description, see [Devine et al, 2006].

A new feature available in Zoltan 3.0 is the ability to assign selected objects (vertices) to a particular part ("fixed vertices"). When objects are fixed, Zoltan will not migrate them out of the user assigned part. See the descriptions of the ZOLTAN_NUM_FIXED_OBJ_FN and ZOLTAN_FIXED_OBJ_LIST_FN query functions for a discussion of how you can define these two functions to fix objects to parts. Both PHG and PaToH support this feature.

For applications that already use Zoltan to do graph partitioning, it is easy to upgrade to hypergraph partitioning. For many applications, the hypergraph model is superior to the graph model, but in some cases the graph model should be preferred. PHG can also be used as a pure graph partitioner. See the section graph vs. hypergraph partitioning for further details.