METIS

Introduction

METIS is a library, and an associated set of executable programs, for the partitioning of graphs and meshes, and for the reordering of sparse matrices.

Most users will be interested in running one of the executable programs associated with the METIS library, rather than using the library directly. These programs include:

  • cmpfillin, takes a graph and a reordering and computes the fillin.
  • gpmetis, for partitioning the nodes of a graph;
  • mpmetis, for partitioning the elements of a finite element mesh;
  • ndmetis, for reordering the variables in a sparse matrix;
  • m2gmetis, for converting a mesh into the dual or nodal graph;
  • graphchk, for error checking a graph file;

Advanced users may prefer to work directly with the METIS library, in which case the partitioning or reordering can be done immediately, as part of a larger and ongoing computation.

A parallel version of METIS is available as well, under the name PARMETIS.

The METIS family of Multilevel Partitioning Algorithms was produced by the lab of George Karypis, who states

"It is our general policy to make these tools available to the research community for use in their own research and/or non-commercial applications."

For further information on licensing and permissions, refer to http://www.cs.umn.edu/~metis, the METIS home page.

Availability

Version 5.1.0 of METIS is installed on Cascades, DragonsTooth and NewRiver; version 5.0.2 is installed on Blueridge, HokieOne, and HokieSpeed.

Usage

METIS requires module commands to load a compiler. On NewRiver, you may choose to load the modules from any one of the following lines:

      gcc/4.7.2   metis/5.1.0
      gcc/5.2.0   metis/5.1.0
      intel/15.3  metis/5.1.0

To check the modules necessary on other systems, start with the command module spider metis.The METIS executables will be added to your path, and can be invoked by name:

      cmpfillin
      gpmetis
      graphchk
      m2gmetis
      mpmetis
      ndmetis

The METIS library can be accessed in the compile and load statements using the switches -I$METIS_INC and -L$METIS_LIB -lmetis.

Examples

The first example uses the gpmetis program to partition into four parts the graph defined in the file 4elt.graph.

#! /bin/bash
#PBS -l walltime=00:05:00
#PBS -l nodes=1:ppn=1
#PBS -W group_list=newriver
#PBS -q open_q
#PBS -j oe

cd $PBS_O_WORKDIR

module purge
module load gcc/5.2.0
module load metis/5.1.0

gpmetis 4elt.graph 4

The second example shows how a user program metis_test.c can be linked with the METIS library.

#! /bin/bash
#PBS -l walltime=00:05:00
#PBS -l nodes=1:ppn=1
#PBS -W group_list=newriver
#PBS -q open_q
#PBS -j oe
#
cd $PBS_O_WORKDIR
module purge
module load gcc/5.2.0
module load metis/5.1.0

gcc -c -I$METIS_INC metis_test.c
gcc metis_test.o -L$METIS_LIB -lmetis -lm
mv a.out metis_test
./metis_test

If you are interested in using METIS on one of the ARC clusters, it is suggested that you download the file containing the information necessary to run these examples and experiment with them first. Download this tar file.