The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

ParMetis 2.0 - A package for graph partitioning

ParMETIS is an MPI-based parallel library that implements a variety of algorithms for partitioning unstructured graphs and for computing fill-reducing orderings of sparse matries. ParMETIS extends the functionality provided by METIS and includes routines that are especially suited for parallel AMR computatins and large scale numerical simulations. The algorithms impelmented in ParMETIS are based on parallel multilevel k-way graph-partitioning algorithms and adaptive repartitioning algorithms.

ParMETIS provides the following four major fuinctions

Graph Partition
  • Computes high quality partitionings of very large graphs quickly.
  • Takes advantage of geometry information (when available) to reduc$ without loss in quality.
Graph Repartit$
  • Computes high quality repartitions of adaptively refined meshes q$
  • Optimizes both the number of vertices that are moved as well as t$ resulting partitioning.
Partitioning R$
  • Improves the quality of partitions produced by other partitioning$
Matrix Reorder$
  • Computes fill-reducing orderings of sparse matrices.
  • Uses a node-based nested dissection algorithm that has been shown$ outperform other popular reordering algorithms.

  • Download Files (local site)
  • ParMetis Webpage

    Problem Links

    Graph Partition (9)
    Generating Partitions (7)
    Polygon Partitioning (4)

    This page last modified on 2008-07-10 .