Documentation Index
Fetch the complete documentation index at: https://mintlify.com/KarypisLab/METIS/llms.txt
Use this file to discover all available pages before exploring further.
ndmetis computes a fill-reducing reordering of the vertices of a graph, which corresponds to reordering the rows and columns of a sparse symmetric matrix. The resulting permutation minimizes the fill-in created during Cholesky or LU factorization. It uses METIS’s multilevel nested dissection algorithm, which recursively finds vertex separators and orders them last within each bisected subgraph.
Usage
| Argument | Description |
|---|---|
graphfile | Path to the graph file whose vertices are to be reordered. |
The input graph must have exactly one balancing constraint. Graphs with multiple constraints are not supported by the ordering algorithm.
Output Files
ndmetis writes two files derived from the input filename:
| File | Contents |
|---|---|
<graphfile>.iperm | Inverse permutation: iperm[i] is the new position of old vertex i. |
<graphfile>.perm | Forward permutation: perm[j] is the old vertex index at new position j. |
Using the Permutation with Sparse Solvers
Most sparse direct solvers accept a reordering in one of two forms. METIS produces both:Reorder the matrix
Apply
iperm to permute rows and columns of your matrix A into a new matrix A' with less fill: reorder row/column i to position iperm[i].Factor the reordered matrix
Factorize
A' = P A P^T using your sparse Cholesky or LU solver. The factorization of A' has significantly fewer nonzeros than factorizing A directly.Example
Options Reference
Coarsening
Vertex matching scheme used during graph coarsening.
| Value | Description |
|---|---|
shem | Sorted heavy-edge matching (default) |
rm | Random matching |
Disables 2-hop matchings during coarsening. By default, METIS uses 2-hop matchings as a fallback when standard matching cannot sufficiently reduce the graph size. This flag disables that fallback.
Disables vertex compression before ordering. By default, METIS identifies and merges vertices with identical adjacency lists before computing the ordering, which can significantly speed up the process for graphs with many such vertices. Pass this flag to disable that compression step.
Initial Separator
Method used to compute the initial vertex separator at each level of bisection.
| Value | Description |
|---|---|
node | Greedy node-based separator strategy (default) |
edge | Derive vertex separator from an edge cut |
Refinement
Refinement algorithm for improving vertex separators during uncoarsening.
| Value | Description |
|---|---|
1sided | 1-sided node-based refinement (default) |
2sided | 2-sided node-based refinement |
Maximum number of refinement iterations applied at each level of the uncoarsening process.
Number of vertex separators to compute at each level of nested dissection. The smallest separator found is used. Increasing this value improves ordering quality at the cost of additional computation.
Load Balance
Maximum allowed load imbalance between the left and right subgraphs at each bisection, expressed as an integer
x where the actual tolerance is 1 + x/1000. The default of 200 corresponds to a tolerance of 1.20 (20% imbalance).Minimum degree threshold for ordering high-degree vertices last. Any vertex with degree greater than
0.1 * pfactor * (average_degree) is removed, the remaining graph is ordered, and the removed vertices are appended at the end of the ordering. A value of 0 (the default) disables this behavior.Graph Preprocessing
Identifies connected components of the graph and orders each component independently before combining the results. Useful for graphs that are not fully connected.
Memory and I/O
Stores intermediate coarsened graphs to disk during coarsening to reduce peak memory usage. Useful for very large sparse matrices where memory is the primary constraint.
Suppresses writing the
.iperm and .perm output files. Statistics and fill-in estimates are still printed to stdout.Reproducibility and Diagnostics
Seed for the random number generator. The default of
-1 uses a time-based seed. Set an explicit value for reproducible orderings.Debug verbosity level. Set to
0 for no debug output (default). Higher values enable internal diagnostic messages from the ordering algorithm.