Robust preconditioning for indefnite and Ill-conditioned sparse linear systems

Abstract

Linear systems originating from certain applications in the physical sciences can be challenging to solve by iterative methods. In the past, direct methods like Gaussian elimination have been often used to solve these systems, due to their robust nature. However, as problems are now often formulated in 3-D geometries, the use of direct solvers is becoming prohibitive. Moreover, unlike iterative solvers, direct solvers cannot be easily parallelized. Two classes of methods have attracted the interest of researchers in recent years. First, is the class of multigrid methods, which have been shown to be very efficient for elliptic-type problems, and for which various adaptations have been brought. Second, is the class of preconditioned Krylov subspace methods. Here, work has focused mainly on improving the preconditioning. The underlying challenge is to develop or identify techniques that are robust and efficient in terms of accuracy, stability, and scalability. As problems in computational science continue to evolve, so do preconditioning techniques, as new ideas are incorporated to develop solver technologies that are well adapted to solve novel and challenging problems. To further contribute to this endeavor, my research uses ideas from numerical linear algebra to address algorithmic and computational issues in the numerical solution of application problems. The ideas presented in this thesis will focus on improving the stability and effectiveness of ILU-based preconditioners to better handle challenging problems characterized by indefinite and poorly conditioned linear systems. First, we present various strategies designed to improve the quality of the ILU factorization in order to safeguard stability without compromising the accuracy of the resulting factors. These strategies introduce new contributions to the areas of shifted ILU methods, modified ILU and compensation-based techniques, and reordering techniques for ILU. The resulting factors yield good and more robust preconditioners that are effective on highly indefinite and ill-conditioned linear systems. Next, we demonstrate the effectiveness of combining ILU factorizations with multilevel methods. Multilevel ILU methods have become a popular area of research, as researchers seek to take advantage of the superior robustness of ILU, coupled with the efficiency and scalability of multilevel methods. We discuss issues related to constructing the next-level matrices in the multilevel hierarchy and present ideas from multilevel graph coarsening and reordering strategies to construct an algebraic multilevel ILU-based preconditioner. Finally, we discuss key concepts necessary for an efficient adaptation of the ILU-based preconditioner into a parallel framework. We discuss the parallel implementation within the structure of the parallel algebraic multilevel solver (pARMS) framework. We demonstrate how different preconditioning techniques may be incorporated into this framework, and discuss issues relating to scalability.