##
Graph vs Hypergraph Partitioning

Graph partitioning has proven quite useful in scientific computing.
Hypergraph partitioning
is a more recent improvement
that uses a hypergraph model, which is
often a more accurate model than the graph model for scientific computing.
(Hypergraphs contain hyperedges which connect two *or more*
vertices.)
See [Catalyurek & Aykanat] and
[Hendrickson & Kolda]
for further details.
You do not need to understand the underlying models
to use graph or hypergraph partitioning for load-balancing
in Zoltan. The basic trade-offs are:
- Hypergraph partitioning usually produces partitions (assignments)
of higher quality than graph partitioning, which may reduce
communication time in parallel applications (up to 30-40%
reduction has been reported). However, hypergraph
partitioning takes longer time to compute.
- The graph model is restricted to symmetric data dependencies.
If you have a non-symmetric problem, we recommend hypergraph
partitioning.

### Migrating from ParMetis to PHG in Zoltan

If you already use Zoltan for graph partitioning (via ParMetis),
there are three ways to switch to the Zoltan-PHG hypergraph partitioner:
- The quick and easy way: Just change the
LB_METHOD to "Hypergraph".
Zoltan will then use the graph query functions (presumably
already implemented) to construct a hypergraph model, which
is similar to but not equivalent to the graph.
- The proper way: Change the LB_METHOD, but also implement and
register the
hypergraph query functions
required by Zoltan. These may give a more accurate representation
of data dependencies (and communication requirements) for your
application.
- If you really want graph (not hypergraph) partitioning:
Just change the
LB_METHOD to "Graph".
Zoltan will then use PHG as a graph partitioner, which is slower than
ParMetis but often produces better partitions (lower cuts).

Technical note: A hypergraph is constructed from the graph as follows:
The vertices are the same in the hypergraph as in the graph. For each vertex
*v*, create a hyperedge that consists of all neighbors in the graph
and *v * itself.

[Table of Contents |
Next: ParMETIS |
Previous:
Graph Partitioning | Privacy and Security]