METIS - Serial Graph Partitioning and Fill-reducing Matrix Ordering
Frequently Asked Questions (with answers)
- How can I partition directed graphs?
- Why am I getting non-contiguous partitions with METIS?
- How can I compute an envelope reducing ordering?
- My mesh contains element types that are not supported by METIS. Can I still use METIS to partition this mesh?
- I have a mesh with mixed elements. Can I still use METIS to partition this mesh?
- How can I tell which version of METIS am I using?
- Can I distribute METIS with my application?
How can I partition directed graphs?
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.
Back to Top
Why am I getting non-contiguous partitions with METIS?
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.
Back to Top
How can I compute an envelope reducing ordering?
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.
Back to Top
My mesh contains element types that are not supported by METIS. Can I still use METIS to partition this mesh?
METIS currently supports only four basic element types: triangles, quadrilaterals, tetrahedrons, and hexahedrons. If your mesh contains other types of elements, you can still use METIS's graph partitioning routines to partition your mesh. To do that you have to write a program (or use one that you may have already developed) that from your mesh it generates the corresponding nodal or dual graph. You can then use METIS to partition this graph.
Back to Top
I have a mesh with mixed elements. Can I still use METIS to partition this mesh?
METIS's mesh partitioning routines require that the entire mesh consists of only one of the four supported element types. If you mesh consist of mixed types of elements, you must write your own routine to generate the corresponding nodal or dual graph and use METIS's partitioning routines to partition this graph.
Back to Top
How can I tell which version of METIS am I using?
The version number of METIS is contained in the file called "VERSION" in METIS's root directory.
Back to Top
Can I distribute METIS with my application?
Our policy regarding the distribution of METIS with third-party applications is as follows:
- Non-commercial applications
- METIS can be freely distributed provided that:
- Proper references are included.
- The original documentation and copyright notice is included.
- Commercial applications
- METIS can be freely distributed provided that:
- Proper references are included.
- The original documentation and copyright notice is included.
- METIS is a relatively small portion of the overall application.
In either case, permission to distribute/include METIS with your application must be obtained by sending email to metis@cs.umn.edu.