ONMETIS
Reorder Variables in a Sparse Matrix

ONMETIS is a C program which can reorder the variables (rows and columns) in a sparse matrix, so as to produce less fill in during direct elimination.

It is assumed that the sparse matrix is described abstractly by its adjacency graph. OEMETIS reads a file, stored in the METIS GRAPH format, describing the adjacency graph of the sparse matrix, and computes a permutation of the nodes (= variables = rows and columns) that will produce less fill in.

Usage:

To reorder the nodes of a graph that represents a sparse matrix, and thereby minimize fill during elimination:

onmetis graph_file

reads the adjacency information in graph_file, and writes a reordering in graph_file.iperm.

Related Programs:

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

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

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

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

METIS is a library of routines for partitioning the nodes of a graph, or the elements of a finite element mesh, or for reordering the variables in a sparse matrix.

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

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

PARTNMESH is an executable program, using METIS, 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 program, using METIS, which can partition the nodes of a graph.

Reference:

1. metis.pdf,
   George Karypis and Vipin Kumar,
   METIS, a Software Package for Partitioning Unstructured Graphs and Computing Fill-Reduced Orderings of Sparse Matrices;
2. George Karypis and 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:

• onmetis.c
• onmetis.csh, commands to compile the source code and create the library.

Examples and Tests:

• 4elt.graph, a sample graph.
• 4elt.graph.iperm, the reordering computed by OEMETIS.
• onmetis_prb.csh, commands to compile, link, load and run the test problem.
• onmetis_prb.out, the output from the test program.

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