Hybrid Reordering Strategies for ILU
Preconditioning of Indefinite Sparse Matrices

Eun-Joo Lee, and Jun Zhang
Laboratory for High Performance Scientific Computing and Computer Simulation
Department of Computer Science
University of Kentucky
Lexington, KY 40506-0046, USA

Abstract

Incomplete LU factorization preconditioning techniques often have difficulty on indefinite sparse matrices. We present hybrid reordering strategies to deal with such matrices, which include new diagonal reorderings that are in conjunction with a symmetric nondecreasing degree algorithm. We first use the diagonal reorderings to efficiently search for entries of single element rows and columns and/or the maximum absolute value to be placed on the diagonal for computing a nonsymmetric permutation. To augment the effectiveness of the diagonal reorderings, a nondecreasing degree algorithm is applied to reduce the amount of fill-in during the ILU factorization. With the reordered matrices, we achieve a considerably improved the stability of incomplete LU factorizations. Consequently, we reduce the convergence cost of the preconditioned Krylov subspace methods on solving the reordered indefinite matrices.


Key words: Sparse matrix, preconditioning, reordering.

Mathematics Subject Classification: 65F10, 65F50, 65N55, 65Y05.


Download the compressed postscript file joo1.ps.gz, or the PDF file joo1.pdf.
This paper has been accepted for publication in Journal of Applied Mathematics and Computing.

Technical Report 436-05, Department of Computer Science, University of Kentucky, Lexington, KY, 2005.

The research work of J. Zhang was supported in part by the U.S. National Science Foundation under grants CCR-0092532, and ACR-0202934, by the U.S. Department of Energy Office of Science under grant DE-FG02-02ER45961, and by the University of Kentucky Faculty Research Support Program.