METIS - Serial Graph Partitioning and Fill-reducing Matrix Ordering

History of Changes

Ver: 5.1.0, March 30th, 2013
  • Further extended the 2-hop coarsening scheme introduced in 5.0.2 for for graphs with highly variable degree distribution (e.g., power-law). This coarsening scheme is automatically used when the standard 1-hop-based scheme leaves a large fraction of the vertices of the graph unmatched. It leads to better quality partitionings, lower memory utilization, and faster execution time. In principle, this scheme will never be triggered for graphs/matrices appearing in scientific computations derived from FE meshes. However, if you notice that the quality of the solutions is significantly worse, this 2-hop matching can be turned off by using the '-no2hop' command line option and the associated options[] parameter (as described in the manual).
  • Fixed 0/1 numbering issue with mesh partitioning routines (flyspray issue #109)
Ver: 5.0.3, March 11th, 2013
  • Fixed a bug that was introduced in 5.x for creating nodal graphs from meshes.
  • Changed the license to Apache Version 2.
Ver: 5.0.2, October 31th, 2011
  • Fixed issue with high-degree vertices and mask-based compression.
  • Fixed issue with wrong COARSENING_FRACTION.
  • Modified coarsening schemes to better support non FE graphs.
Ver: 5.0.1, August 31th, 2011
  • Fixed critical bug in the mesh partitioning routines. The bug does not affect ParMetis.
Ver: 5.0, August 4th, 2011
  • Updated/corrected error messages.
  • Addressed some build issues.
Ver: 5.0rc3, July 13th, 2011
  • Fixed various bugs that were identified by testers.
  • Some minor performance and quality improvements.
  • Addressed some build issues.
Ver: 5.0rc2, July 6th, 2011
  • Various run-time and quality optimizations.
  • Option error-checking.
  • Signal-based heap cleanup on error. Metis API routines will not return nicely and cleanup all memory that may have allocated.
  • Reduced memory requirements.
  • Fixed various bugs identified in rc1.
  • Added back Fortran support in the form of alternate API names (see libmetis/frename.h).
  • Minor code changes to accommodate ParMetis 4.0.
Ver: 5.0rc1, June 14th, 2011
  • A nearly complete re-write of Metis' code-based that changed expanded the functionality of the command-line programs and API routines.
  • Multi-constraint partitioning can be used in conjunction with minimization of the total communication volume.
  • All graph and mesh partitioning routines take as input the target sizes of the partitions, which among others, allow them to compute partitioning solutions that are well-suited for parallel architectures with heterogeneous computing capabilities.
  • When multi-constraint partitioning is used, the target sizes of the partitions are specified on a per partition-constraint pair.
  • The multilevel k-way partitioning algorithms can compute a partitioning solution in which each partition is contiguous.
  • All partitioning and ordering routines can compute multiple different solutions and select the best as the final solution.
  • The mesh partitioning and mesh-to-graph conversion routines can operate on mixed element meshes.
  • The command-line programs provide full access to the entire set of capabilities provided by Metis' API.
  • Re-written the memory management subsystem to reduce overall memory requirements.
Ver: 4.0.3, March 19th, 2011
  • Renamed log2() to ilog2() to remove conflicts with C99 log2() function.
  • Fixed I/O and error-reporting routines to eliminate compilation warnings.
Ver: 5.0pre2, April 8th, 2007
  • Fixed a number of bugs with the 64bit support and added some basic build instructions. The new code has been reasonably well-tested under Linux and GCC. However, more testing is needed on different architectures.
  • Portable I/O on both 32- and 64-bit architectures.
  • There were a few major reorganization in the internals of the code. It now utilizes a home-grown library of helper routines. This will enable the library on fatal errors to release the memory to the application and gracefully return to the calling program. This will probably be enabled in the near future.
  • A compiler that supports C99 is now required.
Ver: 5.0pre1, March 2007
  • Initial support for 64 bit architectures (see include/metis.h)
  • Fixed some bugs that appeared over the years (still work in progress)
  • Unified unix/windows build (requires Gnu's make on windows)
Ver: 4.0.2, March 10th, 2004
  • Fixed a problem with weighted graphs and ordering.
Ver: 4.0.1, November 1998
  • Fixed some bugs with the multi-constraint partitioning routines.
  • Fixed some bugs with the partitioning routines that directly minimize the total communication volume.
Ver: 4.0.0, September 1998
  • Added partitioning routines that can compute a k-way partitioning in the presence of multiple balancing constraints.
  • Added partitioning routines whose objective is to directly minimize the total communication volume of the partitioning.
  • Added routines that directly minimize the maximum and the overall connectivity of the subdomains.
  • Added routines that reduce the number of non-contiguous subdomains.
Ver: 3.0.6, January 1998
  • Fixed some problems when too many partitions were asked, and each partition end up having 0 vertices
  • Fixed some bugs in the I/O routines
  • Added support for the g77 compiler under Linux
Ver: 3.0.5, December 1997
  • Fixed problems on 64-bit architectures (e.g., -64 option on SGIs)
  • Added some options in Makefile.in
Ver: 3.0.4, December 1997
  • Fixed a memory leak in the ordering code
Ver: 3.0.3, December 1997
  • Added support for quadrilateral elements
  • Added a routine METIS_EstimateMemory that estimates the amount of memory that will be allocated by METIS. This is useful in determining if a problem can run on your system
  • Added hooks to allow PARMETIS to use the orderings produced by METIS. This is hidden from the user but it will be used in the next release of PARMETIS
  • Fixed a bug related to memory allocation. This should somewhat reduce the overall memory used by METIS
  • Fixed some bugs in the 'graphchk' program in the case of weighted graphs
  • Removed some code corresponding to unused options
  • Fixed some minor bugs in the node-refinement code
Ver: 3.0.0, October 1997
  • Added partitioning routines that can be used to compute a partition with prescribed partition weights. For example, they can be used to compute a 3-way partition such that partition 1 has 50% of the weight, partition 2 has 20% of the way, and partition 3 has 30% of the weight.
  • Improved the speed of the k-way partitioning algorithm. The new code has better cache locality which dramatically improves the speed for large graphs. A factor of 4 speedup can be obtained for certain graphs. METIS can now partition in 256 parts, a 4 million node graph in well under a minute on a MIPS R10000.
  • METIS can now directly partition the element node array of finite element meshes. It produces two partitioning vectors. One for the elements and one for the nodes. METIS supports the following elements: triangles, tetrahedral, hexahedral, quadrilaterals.
  • METIS now includes a number of mesh conversion functions that can be used to create the dual and nodal graphs directly from the element connectivity arrays. These are highly optimized routines.
  • Added a node based ordering code that greatly improves ordering quality.
  • Improved the quality of the orderings produced by the original edge-based ordering code.
  • METIS can now analyze the graph and try to compress together nodes with identical sparsity pattern. For some problems, this significantly reduces ordering time.
  • Added better support for ordering LP matrices.
  • The names, calling sequences, and options of the routines in METISlib have been changed.
  • Better support has been added for Fortran programs.
  • Better support for weighted graphs.