OEMETIS
Reorder Variables in a Sparse Matrix

OEMETIS 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:

oemetis graph_file

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

Related Programs:

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

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

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

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

METIS is a C 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.

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

METIS_MESH is a data directory which 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 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.

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

PARTNMESH is a C 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 a C 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:

• oemetis.c
• oemetis.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.
• oemetis_prb.csh, commands to compile, link, load and run the test problem.
• oemetis_prb.out, the output from the test program.

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