ParMETIS - Mesh Graph Partitioning Algorithm

Partitioning and Repartitioning Unstructured Graphs and Computing Fill-Reducing Orderings of Sparse Matrices

ParMETIS is an MPI-based parallel library that implements a variety of algorithms for partitioning and repartitioning unstructured graphs and for computing fill-reducing orderings of sparse matrices. ParMETIS is particularly suited for parallel numerical simulations involving large unstructured meshes. In this type of computation, ParMETIS dramatically reduces the time spent in communication by computing mesh decompositions such that the numbers of interface elements are minimized.

ParMETIS Extends the Functionality Provided by METIS

The algorithms in ParMETIS are based on the multilevel partitioning and fill-reducing ordering algorithms that are implemented in the widely-used serial package METIS.  However, ParMETIS extends the functionality provided by METIS and includes routines that are especially suited for parallel computations and large-scale numerical simulations.  In particular, 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 algorithm

PARMETIS BENEFITS

• Fast - Less than a minute required to partition graphs with millions of vertices on a workstation
• High Quality - Results in substantial reduction in edge-cut or fill compared to other schemes for a variety of graphs
• Parallel - 8M-vertex graph takes under 3 seconds to partition on a 256-processor Cray T3E
• Used Extensively - National labs, industry, academic institutions worldwide