METIS - Serial Graph Partitioning and Fill-reducing Matrix Ordering
- How can I partition directed graphs?
- Why am I getting non-contiguous partitions with METIS?
- How can I compute an envelope reducing ordering?
- Can I distribute METIS with my application?
- How to cite METIS?
The partitioning routines in METIS can only partition undirected graphs (i.e., graphs in which for each edge (v,u) there is also an edge (u,v)). For partitioning purposes, the directionality of an edge does not play any role because if edge (u,v) is cut so will the edge (v,u). For this reason, a directed graph can be easily partitioned by METIS by first converting it into the corresponding undirected graph. That is, create a graph for each directed edge (u,v) also contains the (v,u) edge as well.
The partitioning routines in METIS do not guarantee that the partitions are contiguous. In most cases, the partitions produced by METIS will be contiguous. However, depending on the underlying geometry and the size of the graph relative to the number of partitions, some of the partitions my not be contiguous. From version 5.0, Metis provides support for enforcing the partitions to be contiguous by using the -contig option.
METIS's fill-reducing ordering routines are suitable for general sparse direct factorization algorithms and they are not suitable for envelope-based factorization. METIS's routines cannot be used to compute orderings that minimize the envelope of a sparse matrix.
METIS as of 5.0.3 is being distributed under the Apache License Version 2.0.
“A Fast and Highly Quality Multilevel Scheme for Partitioning Irregular Graphs”. George Karypis and Vipin Kumar. SIAM Journal on Scientific Computing, Vol. 20, No. 1, pp. 359—392, 1999.