ParMETIS - Parallel Graph Partitioning and Fill-reducing Matrix Ordering

Current stable version: 4.0.3, 3/30/2013

ParMETIS is an MPI-based parallel library that implements a variety of algorithms for partitioning unstructured graphs, meshes, and for computing fill-reducing orderings of sparse matrices. ParMETIS extends the functionality provided by METIS and includes routines that are especially suited for parallel AMR computations and large scale numerical simulations. The algorithms implemented in ParMETIS are based on the parallel multilevel k-way graph-partitioning, adaptive repartitioning, and parallel multi-constrained partitioning schemes developed in our lab.

ParMETIS provides the following five major functions:

Graph Partitioning
  • Computes high quality partitionings of very large graphs quickly.
  • Takes advantage of geometry information (when available) to reduce the partitioning time without loss in quality.
  • Can partition graphs for multi-phase and multi-physics computations.
Mesh Partitioning
  • Computes high quality partitionings of very large meshes directly, without requiring the application to create the underlying graph.
  • Provides highly efficient parallel routines for generating the dual graph of a mesh.
Graph Repartitioning
  • Computes high quality repartitions of adaptively refined meshes quickly.
  • Optimizes both the number of vertices that are moved as well as the edge-cut of the resulting partitioning.
Partitioning Refinement
  • Improves the quality of partitions produced by other partitioning algorithms.
Matrix Reordering
  • Computes fill-reducing orderings of sparse matrices.
  • Uses a node-based nested dissection algorithm that has been shown to significantly outperform other popular reordering algorithms.