METIS is a set of programs and a C library for partitioning graphs, partitioning finite element meshes, and producing fill-reducing orderings for sparse matrices. Developed at the University of Minnesota by George Karypis, METIS implements state-of-the-art multilevel recursive-bisection, multilevel k-way, and multi-constraint partitioning algorithms that produce high-quality results quickly even for very large graphs.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.
Installation
Build METIS from source and install the library and CLI tools on your system.
Quickstart
Partition your first graph in minutes using the CLI or the C API.
API Reference
Complete reference for all public METIS API functions with parameters and return values.
CLI Tools
Reference for gpmetis, ndmetis, mpmetis, and other command-line programs.
What METIS does
METIS solves three related problems in high-performance scientific computing: Graph partitioning — Divides a graph into k roughly equal parts while minimizing the number of edges between parts (edge-cut) or total communication volume. This is critical for distributing parallel finite element computations across processors. Mesh partitioning — Directly partitions finite element meshes (triangles, tetrahedra, hexahedra, and mixed meshes) into balanced subdomains, producing both element-partition and node-partition vectors. Fill-reducing ordering — Computes permutations for sparse symmetric matrices that minimize fill-in during Cholesky or LU factorization, dramatically reducing memory and computation in direct solvers.Key capabilities
Multilevel k-way partitioning
Direct k-way partitioning using the multilevel paradigm: coarsen → initial partition → refine. Scales to graphs with tens of millions of vertices.
Recursive bisection
Recursive bisection for 2^n partitions with provably good edge-cut minimization. Preferred for small partition counts.
Multi-constraint partitioning
Partition graphs with multiple vertex weights simultaneously, ensuring balance across all constraints — essential for heterogeneous parallel workloads.
Nested dissection ordering
Fill-reducing orderings via nested dissection for use with direct sparse linear solvers like CHOLMOD, SuperLU, and PARDISO.
Mesh-to-graph conversion
Convert element-node connectivity arrays into dual or nodal graphs for use in graph partitioning routines.
Fortran bindings
All API functions are available through Fortran name variants (uppercase, lowercase, and underscore-suffixed forms).
Project structure
| Component | Description |
|---|---|
libmetis/ | Core library (~45 source files implementing all algorithms) |
include/metis.h | Public API header — types, enums, and function prototypes |
programs/ | Six standalone CLI programs wrapping the library |
graphs/ | Sample graph and mesh files for testing |