Advances in Robust Multilevel Preconditioning Methods for Sparse Linear Systems

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

Solving linear systems of equations is at the heart of many large scale numerical simulations in sciences and engineering. These systems can have tens or hundreds of millions simulations in the aerodynamic design of airplanes and equilibrium models in macro-economics. In most common situations, the equations encountered in these applications are 'sparse' in the sense that each equation involves a small number of unknowns or parameters. This project is about the effective solution of such systems by a class of methods that are termed 'iterative'. An iterative method does not attempt to compute an exact solution by the age-old method of elimination. Instead, it generates a sequence of approximations that gradually approaches the solution. However, in spite of the numerous advances made in past decades in iterative solution methods for linear systems, practitioners still face difficulties when applying these methods to certain types of problems. The proposal aims at advancing the state-of-the art in a specific class called Preconditioning Krylov subspace methods. In essence, the techniques proposed combine preconditioners (making the problem easier to solve by exploiting approximate elimination), with good acceleration methods (combining successive iterates to accelerate convergence) and Domain Decomposition ideas (decomposing the problem into parts so as to exploit parallel treatment of each part). This project focuses on the class of Preconditioned Krylov Subspace Methods (PKSMs) for solving linear systems of equations. These methods try to reach a compromise between generality and efficiency by combining an accelerator (e.g., GMRES) and a preconditioner (e.g., Incomplete LU or Algebraic Multi-Grid). It is now well-known that the preconditioner holds the key to the success of this combination. The primary goal of this project is to address the two most important weaknesses of these methods. Their first weakness is their lack robustness in some situations, e.g., when the linear system at hand is highly indefinite or ill-conditioned. In the past researchers have often limited their attention to diagonally dominant systems that arise from discretizing Poisson-like equations. However, the more realistic problems addressed by engineers and scientists have become much harder to solve, leading to a demand for new types of preconditioners. The second weakness of iterative methods is that preconditioners have traditionally been developed with sequential environments in mind, and therefore they often perform poorly in parallel environments. An effort must be made to develop better, more scalable, parallel methods by adopting a view-point that is based on domain-decomposition from the start. To improve the parallel efficiency of preconditioners it is vital to incorporate ideas that exploit a multilevel paradigm. A second avenue to be explored in this project aims primarily at improving robustness by a class of methods that will extend and optimize a strategy based on the Cauchy integral formula for developing preconditioners. The starting point of the project is to expand the PI's research on Multi-Level Low-Rank (MLR) approximation techniques, focusing on a parallel Domain Decomposition framework. MLR techniques have shown a great potential in addressing the issues raised above. First, they rely on an approximate inverse viewpoint and as such these methods tend to be far more robust than their Incomplete LU (ILU) counterparts. They can handle highly indefinite linear systems, such as those arising from wave scattering simulations, more effectively than existing methods. Second, MLRs do not require factorizations and are excellent candidates for high-performance computers, e.g., ones equipped with Graphical Processing Units (GPUs). Finally, they are easy to update in that it is inexpensive to augment or refine them in order to improve their accuracy in the situation when their observed performance is not satisfactory. Different ways to define low-rank approximations will be explored which are all rooted in the Domain-Decomposition framework and Schur complement techniques. The second part of the planned work is to consider extensions of the idea of incorporating complex shifts when solving linear systems. The techniques to be developed here will aim specifically at highly indefinite systems such as those that arise from wave propagation phenomena (Helmholtz, Maxwell). The broader impacts of this project include the free distribution of general purpose codes developed by the PI's research team, and the training of graduate and undergraduate students at a time where demand for specialists in computational mathematics is strong. Among other training activities, the PI will continue the practice of freely disseminating books (two books currently available), lecture notes (three courses currently posted), and MATLAB scripts for educational purposes, as these can play a major role in promoting knowledge and know-how in the theory and application of numerical linear algebra. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.