METIS means Serial Graph Partitioning and Fill-reducing Matrix Ordering, which is a set of serial programs for partitioning graphs, partitioning finite element meshes, and producing fill reducing orderings for sparse matrices. The algorithms implemented in METIS are based on the multilevel recursive-bisection, multilevel k-way, and multi-constraint partitioning schemes developed in our lab.
For original papers, please refer to Graph Partitioning for High Performance Scientific Simulations and Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix Vector Multiplication.
METIS is one example of using alternative way to solving real-world problem. Consider graphs like road network is huge, apply partition algorithms like kernighan_lin directly might never get result. METIS will first simplify graph into a smaller one, then apply partition algorithm, then try to adjust partition result by adding selected elements back.
- Coarsen the graph by collapsing heavy edges. Vertex weights and edge weights are updated. Vertex and edge weights are initially 1.
- Repeat until the graph is small enough, then partition the coarsest level graph by some method.
- Uncoarsen. After each uncoarsening step, refine the partition (using, e.g., Kerninghan-Lin).
For more information, please take a look at this and original papers.
One way to coarsen the graph:
