Home » Research » Software

METIS - Family of Multilevel Partitioning Algorithms

METIS is a family of programs for partitioning unstructured graphs and hypergraphs and computing fill-reducing orderings of sparse matrices. The underlying algorithms used by METIS are based on the state-of-the-art multilevel paradigm that has been shown to produce high quality results and scale to very large problems.

The METIS family consists of three different packages:
 

METIS - Serial Graph Partitioning and Fill-reducing Matrix Ordering
Current version: 4.0.1, 11/30/98 [Alpha version: 5.0pre2, 4/8/07]

METIS 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.

»   
ParMETIS - Parallel Graph Partitioning and Fill-reducing Matrix Ordering
Current version: 3.1.0, 8/15/03

ParMETIS is an MPI-based parallel library that implements a variety of algorithms for partitioning unstructured graphs, meshes, and for computing fill-reducing orderings of sparse matrices. ParMETIS extends the functionality provided by METIS and includes routines that are especially suited for parallel AMR computations and large scale numerical simulations. The algorithms implemented in ParMETIS are based on the parallel multilevel k-way graph-partitioning, adaptive repartitioning, and parallel multi-constrained partitioning schemes developed in our lab.

»   
hMETIS - Hypergraph & Circuit Partitioning
Current version: 1.5.3, 11/22/98 [Alpha version: 2.0pre1, 5/24/07]

hMETIS is a set of programs for partitioning hypergraphs such as those corresponding to VLSI circuits. The algorithms implemented by hMETIS are based on the multilevel hypergraph partitioning schemes developed in our lab.

»