PMETIS
Graph Partitioning using METIS

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

Typically, the graph 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.

PMETIS uses multilevel recursive bisection and is best when the number of parts is 8 or less. The related KMETIS program uses k-way partitioning, and is best when the number of parts is more than 8.

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

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

Usage:

To partition the nodes of a graph, minimizing the number of edge cuts:

pmetis graph_file nparts

reads the node adjacency information in graph_file, assigns each node to processor 0 through nparts-1, and writes the partitioning to the file graph_file.part.nparts.

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 which is an alternative program to PMETIS.

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 is a C library which is used by PMETIS.

METIS_GRAPH is a data directory which contains examples of the graph files used to describe a graph 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 a 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.

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:

• pmetis.c
• pmetis.csh, commands to compile, link and load the source code.

Examples and Tests:

• pmetis_prb.csh, commands to get a graph file and use KMETIS to partition it into 8 parts.
• pmetis_prb.out, the printed output from the PMETIS program.
• 4elt.graph, a graph file of 15,606 vertices and 45,878 edges.
• 4elt.graph.part.8, the partition created by PMETIS.

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