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.
All METIS partitioning and ordering functions accept an idx_t options[METIS_NOPTIONS] array that controls algorithm behavior. The array has METIS_NOPTIONS = 40 slots, indexed by the constants of the moptions_et enum. The value -1 in any slot means “use the algorithm’s default for this option.” Always initialize the entire array with METIS_SetDefaultOptions before setting individual entries.
idx_t options[METIS_NOPTIONS];
METIS_SetDefaultOptions(options); /* fills all entries with -1 */
/* Then override what you need */
options[METIS_OPTION_NCUTS] = 3;
options[METIS_OPTION_SEED] = 42;
Partitioning Options
Partitioning scheme. Selects between recursive bisection and direct k-way.| Value | Enum | Description |
|---|
0 | METIS_PTYPE_RB | Multilevel recursive bisection |
1 | METIS_PTYPE_KWAY | Multilevel k-way partitioning (default) |
METIS_PartMeshDual, METIS_PartMeshNodal (to select the underlying graph partitioner). Implicit for METIS_PartGraphKway and METIS_PartGraphRecursive, which have fixed algorithms. Objective function to minimize.| Value | Enum | Description |
|---|
0 | METIS_OBJTYPE_CUT | Minimize edge cut (default for partitioning) |
1 | METIS_OBJTYPE_VOL | Minimize total communication volume (k-way only) |
2 | METIS_OBJTYPE_NODE | Minimize node separator size (ordering only) |
METIS_PartGraphRecursive only supports METIS_OBJTYPE_CUT. METIS_NodeND always uses METIS_OBJTYPE_NODE regardless of this setting. Vertex numbering convention used in the input graph arrays.| Value | Description |
|---|
0 | 0-based (C-style) (default) |
1 | 1-based (Fortran-style) |
1, METIS temporarily renumbers arrays during processing and restores them on return. Number of different partitionings to compute. METIS performs ncuts independent multilevel runs and returns the best result. Higher values improve quality at the cost of runtime.Default: 1
Number of initial partition trials during the initial partitioning phase. More trials improve quality.Default: -1 (METIS selects automatically based on graph size and nparts)
Number of refinement iterations during the uncoarsening phase.Default: 10
Maximum allowed load imbalance expressed as an integer. The actual balance tolerance is 1 + UFACTOR/1000. For example, UFACTOR = 30 allows up to 3% imbalance.Defaults: 30 for k-way partitioning, 1 for recursive bisection (single constraint), 10 for multi-constraint recursive bisection.
Whether to explicitly minimize the maximum subdomain connectivity (the number of neighboring subdomains). Enabling this can increase runtime but typically produces better partitions for iterative solvers.| Value | Description |
|---|
0 | Disabled (default) |
1 | Enabled |
METIS_PartGraphKway. Whether to force contiguous (connected) partitions. When enabled, METIS ensures each partition is a connected subgraph.| Value | Description |
|---|
0 | Disabled (default) |
1 | Enabled |
METIS_PartGraphKway. The input graph must be connected when this option is used; passing a disconnected graph with CONTIG = 1 is an input error. Seed for the random number generator. Set to a fixed non-negative value for reproducible results. Set to -1 to use a time-based seed.Default: -1 (random seed)
Coarsening Options
Coarsening scheme used to reduce the graph.| Value | Enum | Description |
|---|
0 | METIS_CTYPE_RM | Random matching |
1 | METIS_CTYPE_SHEM | Sorted heavy-edge matching (default) |
Whether to disable the 2-hop matching during coarsening. 2-hop matching connects vertices two hops apart in the graph to achieve better coarsening when the direct neighborhood is too small.| Value | Description |
|---|
0 | 2-hop matching enabled (default) |
1 | 2-hop matching disabled |
Alias for controlling 2-hop coarsening behavior in some contexts. See METIS_OPTION_NO2HOP.Default: -1 (use NO2HOP setting)
Whether to compress the graph before ordering by identifying and merging vertices with identical adjacency lists.| Value | Description |
|---|
0 | Disabled |
1 | Enabled (default for NodeND) |
METIS_NodeND. Compression can significantly speed up ordering on graphs with many identical rows (e.g., structured matrices), but is automatically disabled if pruning (METIS_OPTION_PFACTOR) is active. Whether to randomly drop edges during coarsening to speed up the process on very dense graphs.| Value | Description |
|---|
0 | Disabled (default) |
1 | Enabled |
Whether to use out-of-core processing for very large graphs that do not fit in memory.| Value | Description |
|---|
0 | In-memory (default) |
1 | Out-of-core (on-disk) |
Refinement Options
Refinement scheme applied during uncoarsening.| Value | Enum | Description |
|---|
0 | METIS_RTYPE_FM | Fiduccia-Mattheyses 2-way refinement (used by recursive bisection) |
1 | METIS_RTYPE_GREEDY | Greedy k-way refinement (default for k-way) |
2 | METIS_RTYPE_SEP2SIDED | Two-sided node FM separator refinement |
3 | METIS_RTYPE_SEP1SIDED | One-sided node FM separator refinement (default for NodeND) |
METIS_ERROR_INPUT if an incompatible combination is specified. Initial partitioning scheme applied to the coarsened graph.| Value | Enum | Description |
|---|
0 | METIS_IPTYPE_GROW | Greedy grow bisection (default for recursive bisection, single constraint) |
1 | METIS_IPTYPE_RANDOM | Random bisection (default for recursive bisection, multi-constraint) |
2 | METIS_IPTYPE_EDGE | Edge-based separator computation (default for NodeND) |
3 | METIS_IPTYPE_NODE | Node-based separator computation |
4 | METIS_IPTYPE_METISRB | METIS recursive bisection for k-way initial partition (default for k-way) |
Ordering-Specific Options
Number of separators computed at each step of the nested dissection. METIS performs nseps bisections and selects the best separator (smallest weight). Only applicable to METIS_NodeND.Default: 1
Whether to detect connected components after each separator computation and order them independently, rather than treating the two halves as a single left/right subgraph pair.| Value | Description |
|---|
0 | Standard ordering (default) |
1 | Order connected components separately |
METIS_NodeND. Pruning factor for high-degree vertices during ordering. Vertices with degree greater than 0.1 * PFACTOR * (average degree) are removed before ordering and placed last in the ordering. This prevents high-degree “hub” vertices from dominating separator computations.A value of 0 disables pruning (default). Typical non-zero values are in the range 50–200.Only applicable to METIS_NodeND.
Output and Debug Options
Debug output level. This is a bitmask: OR together the values from mdbglvl_et to enable multiple output types simultaneously.| Value | Enum | Description |
|---|
1 | METIS_DBG_INFO | General diagnostic messages |
2 | METIS_DBG_TIME | Timing information |
4 | METIS_DBG_COARSEN | Coarsening progress |
8 | METIS_DBG_REFINE | Refinement progress |
16 | METIS_DBG_IPART | Initial partitioning info |
32 | METIS_DBG_MOVEINFO | Vertex move info during refinement |
64 | METIS_DBG_SEPINFO | Separator refinement moves |
128 | METIS_DBG_CONNINFO | Subdomain connectivity minimization |
256 | METIS_DBG_CONTIGINFO | Connected component elimination |
2048 | METIS_DBG_MEMORY | Workspace allocation info |
0 (no debug output)/* Enable timing and coarsening output */
options[METIS_OPTION_DBGLVL] = METIS_DBG_TIME | METIS_DBG_COARSEN;
When enabled, uses faster but potentially lower-quality algorithms. Intended for large graphs where runtime is the primary concern.Default: -1 (disabled)
Full Initialization Example
#include <metis.h>
void configure_kway_partitioning(idx_t *options, idx_t nparts) {
METIS_SetDefaultOptions(options);
/* Objective: minimize edge cut (default, shown explicitly) */
options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_CUT;
/* Coarsening: sorted heavy-edge matching (default) */
options[METIS_OPTION_CTYPE] = METIS_CTYPE_SHEM;
/* Try 5 cuts, keep the best */
options[METIS_OPTION_NCUTS] = 5;
/* 10 refinement iterations per cut */
options[METIS_OPTION_NITER] = 10;
/* Allow up to 3% imbalance */
options[METIS_OPTION_UFACTOR] = 30;
/* Require contiguous partitions */
options[METIS_OPTION_CONTIG] = 1;
/* Minimize subdomain connections */
options[METIS_OPTION_MINCONN] = 1;
/* Reproducible run */
options[METIS_OPTION_SEED] = 12345;
/* Show timing info */
options[METIS_OPTION_DBGLVL] = METIS_DBG_TIME;
}
void configure_nd_ordering(idx_t *options) {
METIS_SetDefaultOptions(options);
/* Try 3 separators at each bisection, keep the smallest */
options[METIS_OPTION_NSEPS] = 3;
/* Compress identical rows before ordering */
options[METIS_OPTION_COMPRESS] = 1;
/* Prune high-degree vertices (degree > 0.1*100*sqrt(n)) */
options[METIS_OPTION_PFACTOR] = 100;
/* One-sided separator refinement (default, shown explicitly) */
options[METIS_OPTION_RTYPE] = METIS_RTYPE_SEP1SIDED;
}
