ParMETIS is a parallel graph and mesh partitioning library developed at the University of Minnesota. It uses MPI for distributed-memory parallelism, allowing it to scale across clusters and multi-processor systems. The library implements multilevel recursive bisection, multilevel k-way partitioning, and multi-constraint partitioning schemes that produce high-quality partitions with low edge cuts and balanced workloads.Documentation Index
Fetch the complete documentation index at: https://mintlify.com/KarypisLab/ParMETIS/llms.txt
Use this file to discover all available pages before exploring further.
What ParMETIS does
Partitioning a large graph or mesh across MPI processes is a core challenge in parallel scientific computing. ParMETIS accepts a distributed graph or mesh as input and assigns each vertex or element to one of k partitions such that:- The number of edges crossing partition boundaries (edge cut) is minimized.
- Each partition receives a balanced share of the total vertex or edge weight.
- The assignment respects any multi-constraint weight requirements.
Key capabilities
Graph partitioning
Partition distributed graphs using multilevel k-way or geometry-assisted algorithms to minimize edge cuts and balance vertex weights.
Mesh partitioning
Directly partition finite element meshes, or convert a mesh to its dual graph and partition the dual.
Adaptive repartitioning
Dynamically rebalance an existing partition when vertex weights change, as in adaptive mesh refinement simulations.
Matrix ordering
Compute nested dissection orderings that minimize fill-in for sparse direct linear solvers.
How it works
ParMETIS implements the multilevel paradigm:- Coarsening — the graph is successively contracted by matching and merging adjacent vertices until a small, manageable coarse graph is obtained.
- Initial partitioning — the coarse graph is partitioned using an exact or greedy algorithm.
- Uncoarsening and refinement — the partition is projected back through the hierarchy, and a local refinement algorithm (such as Kernighan-Lin/Fiduccia-Mattheyses) improves the partition at each level.
Architecture and dependencies
ParMETIS is a C library (C99) with an MPI-based API. It depends on two other libraries from the same lab:The integer and floating-point data type widths (32-bit or 64-bit) used by ParMETIS are controlled by the
IDXTYPEWIDTH and REALTYPEWIDTH constants defined when METIS is configured. Both libraries must be built with the same widths.Where to go next
Installation
Install prerequisites, clone dependencies, and build ParMETIS from source.
Quickstart
Run a complete parallel graph partitioning example using
ParMETIS_V3_PartKway.API reference
Detailed documentation for every public ParMETIS function.
Concepts
Learn about graph representations, the CSR format, and distributed data structures.