Robust Preconditioning for Spare Linear Systems

Preconditioned iterative methods have become standard linear solvers in many applications, but their limited robustness in some cases has hindered the ability to efficiently solve very large problems in some areas. This thesis proposes several new preconditioning techniques that attempt to extend the range of iterative methods, particularly to solving nonsymmetric and indefinite problems such as those arising from incompressible computational fluid dynamics. First, we present an iterative technique to compute sparse approximate inverse preconditioners. This new technique produces approximate inverses comparable in quality with others in the literature, but at a lower computational cost, and with a simpler method to determine good sparsity patterns for the approximate inverse. This class of preconditioners is very attractive for parallel computing and avoids the stability problems that may occur with incomplete LU (ILU) preconditioners on nonsymmetric or indefinite matrices. Next, we demonstrate more effective uses of approximate inverses than using them to precondition the entire matrix. We show how to use approximate inverse techniques to construct block preconditioners, particularly for the discrete fully-coupled incompressible Navier-Stokes equations and matrices that are partitioned by nonoverlapping domain decomposition. Approximate inverse techniques are used to generate sparse approximate solutions whenever these are needed in forming the preconditioner. The storage requirements for these preconditioners are much less than for ILU preconditioners for many tough, large-scale problems. To try to improve ILU preconditioners, we experimentally analyze their causes of failure, particularly on indefinite linear systems. We categorize the failure modes and design statistics that can be routinely computed to monitor the factorization or determine the cause of failure. Through this better understanding, we show how these causes of failure can sometimes be circumvented through pivoting, reordering, scaling, perturbing diagonal elements, and preserving symmetric structure. Finally, we present an object-oriented framework that implements some of the preconditioning algorithms above. The framework allows different data structures for block matrices to be used with the same preconditioners. Various methods are provided for inverting diagonal or pivot blocks, possibly with an approximate inverse technique