KMETIS
Graph Partitioning using METIS


KMETIS is a C program which partitions the nodes of a graph using the METIS library.

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.

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

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

KMETIS can be executed on a single processor. However, KMETIS 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:

kmetis 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.

Licensing:

KMETIS is part of the METIS family of Multilevel Partitioning Algorithms. It 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.

Languages:

KMETIS is available in a C version.

Related Programs:

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

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

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

METIS, a C library which is used by KMETIS.

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

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

NEIGHBORS_TO_METIS_GRAPH, 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, a 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, a 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, a C program which can partition the elements of a finite element mesh, by working with the dual graph of the mesh.

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

Reference:

  1. 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;

Source Code:

Examples and Tests:

P18 is a dumbbell-shaped region with a uniform mesh created by DISTMESH. There are some intermediate files, not given here, required to convert the triangle file into a METIS graph file.

P18_NONUNIFORM is a dumbbell-shaped region with a nonuniform mesh created by DISTMESH. There are some intermediate files, not given here, required to convert the triangle file into a METIS graph file.

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


Last revised on 23 August 2008.