Symmetric Permutations for I-matrices to Delay and Avoid Small Pivots During Factorization

In this article, we present several new permutations for I-matrices making these more suitable for incomplete LU-factorization preconditioners used in solving linear systems by iterative methods. A general matrix can be transformed by row permutation as well as row and columns scaling into an I-matrix, i.e., a matrix having elements of modulus 1 on the diagonal and elements of modulus of no more than 1 elsewhere. Reordering rows and columns by the same permutation clearly preserves I-matrices. In this article, we consider such reordering techniques which make the permuted matrix more suitable for an incomplete LU-factorization preconditioner than the original I-matrix. We use a multilevel ILUC, an incomplete LU-factorization preconditioner using Crout's implementation of Gaussian elimination without pivoting to test these reorderings. The combination of I-matrix preprocessing with the various algorithms presented here and the multilevel incomplete LU-factorizations forms a powerful preconditioning method for unsymmetric, highly indefinite problems. The C++ code has been made available in the software package ILU++.