METIS
Graph Partioning, Mesh Partitioning, Matrix Reordering

METIS is a C program which can partition a graph, partition a finite element mesh, or reorder a sparse matrix.

Typically, the graph or mesh is being partitioned so that a computational task can be correspondingly divided up among a number of processors for parallel computing. Thus, it is important that each part of the partition have roughly the same number of elements, and that "connections" between distinct partitions be limited, as much as possible, to reduce the amount of interprocess communication necessary.

The reordering of a sparse matrix is done in order to control the size of the active front, and to reduce the number of fill-in entries created during elimination. In this case, the reordering is very useful even when the computation is to be done on a single processor.

METIS consists of a fundamental library, and a number of executable programs (which call appropriate routines from the library), to handle the graph partitioning, mesh partitioning, and matrix reordering tasks. A number of other utilities are also included.

METIS uses particular formats for storing the graph, mesh or matrix data. The formats have extended to include the ability to weight certain items.

METIS can be executed on a single processor. However, METIS includes an MPI interface which allows it to be run in parallel as well.

Most users will be interested in running one of the executable programs associated with the METIS library, rather than using the library directly. For this purpose, you should go to the web pages listed below, which are associated directly with

• kmetis or pmetis, for partitioning the nodes of a graph;
• partdmesh or partnmesh, for partitioning the elements of a finite element mesh;
• oemetis or onmetis, for reordering the variables in a sparse matrix;
• mesh2dual or mesh2nodal, for converting a mesh into the dual or nodal graph;
• graphchk, for error checking a graph file;

Related Programs:

GRAPHCHK is an executable C program which can read a METIS GRAPH file and verify that it has the proper format.

KMETIS is an executable C program, using METIS, which can partition the nodes of a graph.

MESH2DUAL is an executable C program which converts a finite element mesh to a graph, for further processing by KMETIS or PMETIS.

MESH2NODAL is an executable C program which converts a finite element mesh to a graph, for further processing by KMETIS or PMETIS.

METIS_GRAPH is a data directory contains examples of the graph files used to describe a graph to the METIS family of programs.

METIS_MESH is a data directory contains examples of the mesh files used to describe a finite element mesh to the METIS family of programs.

MPI is a message passing interface that allows programs to be written for execution on parallel computers.

NEIGHBORS_TO_METIS_GRAPH is an executable FORTRAN90 program which reads information describing the adjacency relations in a tet mesh, and writes out essentially the same information, but in a format that METIS will accept.

OEMETIS is an executable C program which reads the adjacency graph of a sparse matrix, stored in METIS GRAPH format, and produces a reordering of the nodes to minimize fill.

ONMETIS is an executable C program which reads the adjacency graph of a sparse matrix, stored in METIS GRAPH format, and produces a reordering of the nodes to minimize fill.

PARTDMESH is an executable C program which can partition the elements of a finite element mesh, by working with the dual graph of the mesh.

PARTNMESH is an executable C program which can partition the elements of a finite element mesh, by working with the nodal graph of the mesh.

PETSC is a library of high level mathematical software for the analysis of partial differential equations on parallel systems. PETSC supports and works with the METIS package.

PMETIS is an executable C program which can partition the nodes of a graph.

Reference:

1. metis.pdf,
   George Karypis, Vipin Kumar,
   METIS, a Software Package for Partitioning Unstructured Graphs and Computing Fill-Reduced Orderings of Sparse Matrices;
2. George Karypis, Vipin Kumar,
   A fast and high quality multilevel scheme for partitioning irregular graphs,
   SIAM Journal on Scientific Computing,
   Volume 20, Number 1, 1998, pages 359-392;
3. http://www.cs.umn.edu/~metis,
   The METIS home page;

Source Code:

• defs.h
• macros.h
• metis.h
• proto.h
• rename.h
• struct.h

• balance.c
• bucketsort.c
• ccgraph.c
• coarsen.c
• compress.c
• debug.c
• estmem.c
• fm.c
• fortran.c
• frename.c
• graph.c
• initpart.c
• io.c, some I/O routines.
• kmetis.c
• kvmetis.c
• kwayfm.c
• kwayrefine.c
• kwayvolfm.c
• kwayvolrefine.c
• match.c
• mbalance2.c
• mcoarsen.c
• memory.c
• mesh.c
• meshpart.c
• mfm.c
• mfm2.c
• mincover.c
• minitpart.c
• minitpart2.c
• mkmetis.c
• mkwayfmh.c
• mkwayrefine.c
• mmatch.c
• mmd.c
• mpmetis.c
• mrefine.c
• mrefine2.c
• mutil.c
• myqsort.c
• ometis.c
• parmetis.c
• pmetis.c
• pqueue.c
• refine.c
• separator.c
• sfm.c
• smbfactor.c, symbolic factorization routines needed for sparse matrix variable reordering.
• srefine.c
• stat.c
• subdomains.c
• timing.c
• util.c
• metis.csh, commands to compile the source code and create the library.

Examples and Tests:

• metis_prb.c, an executable test program.
• metis_prb.csh, commands to compile, link, load and run the test problem.

You can go up one level to the C source codes.