Orderings for Incomplete Factorization Preconditioning of Nonsymmetric Linear Systems

Michele Benzi
Scientific Computing Group (CIC-19), MS B256
Los Alamos National Laboratory
Los Alamos, New Mexico 87545, USA

Daniel B. Szyld
Department of Mathematics
Temple University
Philadelphia, Pennsylvania 19122-6094, USA

Arno van Duin
Department of Computer Science
Leiden University, P.O. Box 9512
2300 RA Leiden, The Netherlands


It is often overlooked that preorderings can have a significant effect on the solution of nonsymmetric linear systems of equations. In fact, good preorderings can improve the performance of Krylov subspace methods significantly. Numerical experiments are presented whereby this effect of reorderings on the convergence of preconditioned Krylov subspace methods is shown. The Krylov subspace methods which are studied include GMRES, transpose free QMR and Biconjugate Gradient Stabilized. The preconditioners used in this study are different variants of incomplete factorizations, including incomplete LU and threshold incomplete LU. Some of the ordering methods used in the study are the minimum degree ordering, and the Cuthill-Mckee ordering. These are orderings designed for direct methods, and their use for the preconditioned Krylov methods is not widespread. It is shown that the reverse Cuthill-Mckee and minimum degree orderings can be very beneficial. The benefit can be seen in the reduction of number of iterations and also in measuring the appropriate deviation of the preconditioned operator from the identity.