ParMETIS - Parallel Graph Partitioning and Fill-reducing Matrix Ordering

History of Changes

Ver: 4.0.3, 3/30/2013
  • Fixed various issues related to wavefront diffusion (flyspray #43).
  • Fixed issue related to the serial code for adaptive repartitioning (flyspray #95).
  • Incorporated the latest version of Metis.
Ver: 4.0.2, 10/31/2011
  • Updated cmake files to use mpicc/mpicxx by default and remove MPI auto-detection that has been creating problems.
  • Fixed refinement assert failure for 0 degree vertices.
Ver: 4.0.1, 9/15/2011
  • Fixed issue with geometric partitioning and too few vertices.
  • Fixed memory leak related to progress reporting.
Ver: 4.0, 8/4/2011
  • Switch to collective comm operations in geometric partitioning.
  • Fixed issues with numflag==1 and npes==1.
  • Added Visual studio support.
  • More manual updates.
Ver: 4.0rc1, 7/16/2011
  • Improved the quality of the geometric partitioning routines.
  • Removed the 4K limit on the maximum number of processors for geometric partitioning.
  • Fixed minor bugs that surfaced since 4.0a3.
  • Updated the manual.
Ver: 4.0a3, 7/14/2011
  • Fixed an old and well-hidden bug in the core sparse communication routines.
  • Fixed the mesh partitioning routines, which were broken due to the fact that ParMetis now tracks all memory allocations and frees them at the end of the computations.
Ver: 4.0a2, 7/13/2011
  • Removed MAXNCON and MAX_PES constant dependency.
  • Reduced memory requirements for MPI comm related data structures.
  • Restructuring of the parameter-checking part of the code.
  • Rewrote how ctrl/graph are being setup. Cleaner code; fewer bugs.
  • Fixed some bugs identified by the early testers.
Ver: 4.0a1, June 2011
  • Serial parts of the code are now based on Metis 5.0.
  • Complete 64 bit support that is controlled at build time by setting the width of the idx_t type in metis/include/metis.h
  • Re-wrote the memory management subsystem that ParMetis utilizes to reduce the total amount of memory that it uses and to support graceful exits (to be implemented in the final 4.0).
  • Better support for multi-constraint partitioning with per-constraint unbalance tolerances.
  • Fixed various bugs that were there since 3.0.
Ver: 3.2.0, April 2011
  • Added a new ordering code that incorporates two major improvements in the refinement routines that should give it a performance that is comparable to that of serial Metis. In addition, the new ordering routines eliminate the power of two restriction of the old routines.
  • Addded a new API function ParMETIS_V32_NodeND that exposes the new ordering options to the user. The old API function is still valid and utilizes the new API.
  • Added a logic to switch to ParMETIS_V3_PartKway when the ParMETIS_V3_PartGeomKway is called with more than 4096 processors. This is due to a current limitation of the ParMETIS_V3_PartGeomKway for large number of processors.
  • Fixed various compilation warnings due to the latest glibc version.
  • Better handling of island (multi-)vertices.
  • Fixed a number of reported bugs. The following tasks correspond to the issues reported at
    • Flyspray Task 55: Fixed segfault when graph->nvtxs == 0.
    • Flyspray Task 54: The above fix applies here as well.
    • Flyspray Task 53: Implemented a partial fix. Complete fix in 4.0.
    • Flyspray Task 50: Free-memory write in PartGeomKway.
    • Flyspray Task 38: Removed malloc.h from stdheaders.h
Ver: 3.1.1, November 2008
  • Fixed a number of bugs that have been reported over the years. The following tasks correspond to the issues reported at
    • Flyspray Task 8: Fixed deallocation of user-supplied vsize.
    • Flyspray Task 28: Fixed ParMETIS_V3_Mesh2Dual static arrays.
    • Flyspray Task 30: Fixed 1025 instead of 1024 buckets.
    • Flyspray Task 34: Fixed writting past wspace->core for certain cases.
    • Flyspray Task 35: Fixed issues associated with assumed 0-based indexing.
    • Flyspray Task 36: Fixed mesh 1->0 numbering error.
  • Fixed non-utilization of the user-supplied seed for the parallel ordering code.
Ver: 3.1.0, August 2003
  • The mesh partitioning and dual creation routines have changed to support mixed element meshes.
  • The parmetis.h header file has been restructured and is now C++ friendly.
  • Fortran bindings/renamings for various routines have been added.
  • A number of bugs have been fixed:
    • tpwgts are now respected for small graphs.
    • fixed various divide by zero errors.
    • removed dependency on the old drand48() routines.
    • fixed some memory leaks.
Ver: 3.0.0, March 2002
  • The names and calling sequence of all the routines have changed due to expanded functionality that has been provided in this release.
  • The various adaptive repartitioning routines  have been replaced by a single routine called ParMETIS_V3_AdpativeRepart that implements a unified repartitioning algorithm which combines the best features of the previous routines.
  • Multiple vertex weights/balance constraints are supported for most of the routines. This allows ParMETIS to be used to partition graphs for multi-phase and multi-physics simulations.
  • Support for different speed processors is provided by being able to specify the target sub-domain weights for each of the sub-domains and for each balance constraint.
  • The number of sub-domains has been de-coupled from the number of processors in both the static and the adaptive partitioning schemes.
  • Routines are provided for both directly partitioning a finite element mesh, and for constructing the dual graph of a mesh in parallel.
Ver: 2.0.0, September 1998
  • The names and calling sequence of all the routines have changed to make it easier to call the various routines from Fortran programs. Note that for this release, the old routine names and calling sequences are still supported.
  • The directed diffusion algorithm has been modified to use the better performing wavefront formulation.
  • Two new adaptive repartitioning routines have been added that are based on the remapping paradigm.
  • The number of partitions has been decoupled from the number of processors. you can now use the parallel partitioning algorithms to compute a k-way partitioning independent of the number of processors that you use.
  • The partitioning and ordering algorithms in ParMETIS now utilize portions of the serial METIS library. As a result of this, the quality of the produced partitionings and orderings have been improved.
Ver: 1.0.0, March 1997
  • Added partitioning routines that take advantage of coordinate information. These routines are based on space-filling curves and they are used to quickly compute a initial distribution for PARKMETIS. A total of three routines have been added called PARGKMETIS, PARGRMETIS, and PARGMETIS.
  • Added a fill-reducing ordering routine that is based on multilevel nested dissection. This is similar to the ordering routine in the serial Metis with the difference that is directly computes and refines vertex separators. The new routine is called PAROMETIS and returns the new ordering of the local nodes plus a vector describing the sizes of the various separators that form the elimination tree.
  • Fixed a number of memory leaks.