Metis/PARMetis: Multilevel Partitioning Algorithms

METIS is a family of programs for partitioning unstructured graphs and hypergraphs and computing fill-reducing orderings of sparse matrices. The underlying algorithms used by METIS are based on the state-of-the-art multilevel paradigm that has been shown to produce high quality results and scale to very large problems.

Overview and Purpose

Two variants of METIS are available on the LRZ HPC systems:

  • METIS: Serial graph partitioning and sparse matrix ordering.
    Provides the following key components:

    • Graph partitioning
    • Mesh partitioning
    • Fill-reducing reordering

    This variant is available both as a set of stand-alone programs and as a library.

  • PARMETIS: Parallel graph partitioning and sparse matrix ordering.
    Provides the following key components:

    • Static graph partitioning
    • Dynamic graph partitioning
    • Fill-reducing reordering

    This variant is available both as a set of parallel stand-alone programs and as an MPI-based library.

Origin of the software

The primary person reponsible for the development and maintenance is:

George Karypis (karypis@cs.umn.edu) Assistant Professor
Department of Computer Science and Engineering
Twin Cities Campus
University of Minnesota, Minneapolis, MN

Supported platforms at LRZ

All HPC platforms at LRZ are supported

Due to changes in the partitioning algorithms the results for the most recent version may not be identical with that for older versions of the software, presumably because a different tradeoff between load balancing and mesh quality was decided upon by the METIS developers.

How to use the software

To make either METIS or PARMETIS available, please first load an appropriate environment module:

module load metis

or

module load parmetis

Then, you will be able to use either the available METIS binaries (see entries in $PARMETIS_BIN), or you can compile a parallel application with PARMETIS calls:

mpicc -c $PARMETIS_INC foo.c

(where foo.c references the parmetis.h include file), and

mpicc -o prog.exe foo.o ... $PARMETIS_LIB

Note that the parmetis module depends on the MPI environment currently loaded. If you change over to some other MPI flavor, you need to reload the parmetis module as well.

For purely serial applications (using the metis module) please replace the PARMETIS_* variables by the corresponding METIS_* names and use icc instead of mpicc. In this case, also the parmetis.h include reference must be changed to metis.h.

Further Information and Manuals