Sparse Matrix Reorderings for ILU and ARMS preconditioners

Yousef Saad
Dept. of Computer Science and Engineering
University of Minnesota,
200 Union Street, S.E.,
Minneapolis, MN 55455
Masha Sosonkina
Dept. of Computer Science,
University of Minnesota Duluth,
320 Heller Hall, 1114 Kirby Dr.,
Duluth, MN 55812

In this talk, we will consider the use of reordering techniques in the context of preconditioned Krylov subspace methods for general sparse linear systems. The current consensus is that many of the well-known reordering methods that are most efficient for sparse direct solvers do not perform similarly when they are used in iterative methods. For this reason, it is important to consider techniques which are developed specifically with iterative solvers in mind. First, a reordering method based on minimum spanning tree and shortest path graph algorithms will be discussed. This method uses a model of Gaussian elimination which introduces distances and incorporates weights based on numerical values of a sparse matrix. We will then consider the specific situation when reordering methods are combined with a multilevel ILU method, such as the Algebraic Recursive Multilevel Solver (ARMS) solver. In this context, we will see that standard reorderings perform quite well. Among the techniques considered, we will report some results with the Nested Dissection algorithm (based on Metis), the Multiple Minimun Degree algorithm, the Reverse Cuthill McKee ordering, and the Approximate Minimum Fill algorithm.

* Work supported by NSF/ACR, by ARO, and by the Minnesota Supercomputer Institute.