Iterative Methods and Preconditioners for Systems of Linear Equations

When I worked in high performance computing several years ago I was told that something over three-quarters of supercomputing cycles were consumed with solving linear systems of equations. Naturally, this influenced the design of computer architecture and, indeed, the speed of solving linear equations using Gaussian elimination was a primary benchmark of supercomputer performance.

 

Solving linear equations via Gaussian elimination or related techniques continues to be the method of choice in many situations. But applications arise where approaches like this are no longer practical. They typically involve very large systems, sometimes with sparse matrices, and iterative methods are necessary. Solving partial differential equations (PDEs) numerically via discrete approximation typically involves large and sparse linear systems, and it is here that iterative methods are most appropriate.

 

This book is an introduction to iterative methods and the associated matrix conditioning that is often desirable. Iterative methods begin with an estimate of a solution and then refine it. Gauss developed one such approach.  This is now sometimes called the Gauss-Seidel method. The authors note that Gauss recommended an iterative method when there are more than two unknowns.

 

The primary focus of this book is using iterative methods and preconditioning for solving discretized elliptic PDEs and optimal control problems governed by such equations. The methods are demonstrated on two model problems – a symmetric one arising from the Laplace equation, and a nonsymmetric one coming from an advection-reaction-diffusion problem.  One iterative method for solving the \( n \times n \)  linear system of equations \( Au=f \)  is to split the matrix into \( A = M − N \). \( M \) is chosen to be more easily invertible (the diagonal or upper triangular part of \( A \), for example).  The splitting leads to a stationary iteration \( M u_{k+1} = N u_{k} +f \) for \( k = 0, 1, 2, \ldots \), where an initial guess \( u_{0} \) is used to start the iteration. The method is called stationary because neither \( M \) nor \( N \) depend on k. The iteration then takes the form \( u_{k+1} = u_{k}  + M^{-1} r_{k} \) where \( r_{k} = f- Au_{k} \) is the residual.  The solution \( u_{\infty} \) is then the solution of the preconditioned \( M^{-1} A u = M^{-1} f \).  From there an iteration on the residual \( r_{k} \), the difference \( d_{k}=u_{k+1}-u_{k} \), and the error \( e_{k}=u-u_{k} \) leads to a solution of the original system.

 

After some introductory material and historical background, the authors consider convergence questions for stationary iterative methods along with several variations (e.g., successive overrelaxation). To improve the performance of iterative methods, the authors recommend also incorporating Krylov methods. These are based on an optimality principle and are, for example, designed to minimize the error or the residual for a given number of matrix-vector multiplications. The authors describe several solution techniques that use Krylov methods. These include, for example, steepest descent and conjugate gradient algorithms.  

 

The convergence of iterative methods depends on the spectral properties of the matrix of the linear system, so it is often desirable to use a linear transformation to reduce the spectral radius. Some algebraic conditioning methods are described, but the authors have a special interest in methods that coordinate well with domain decomposition and application of algorithms to subdomains for numerical solution of PDEs.

 

The last section of the book applies the methods they have developed to optimal control problems including optimal control of the Laplace equation. 

 

The authors offer a good deal of historical background (as well as pertinent quotations from inventors of the various methods). Codes in MATLAB for many of these are also provided via a website. The bibliography is extensive and there are many exercises.

 

Although the authors suggest that the book’s material is largely self-contained, it is likely that readers would find the book much more accessible if they had some background at the level Matrix Computations by Golub and van Loan and at least a modest acquaintance with PDEs and their numerical solutions.

---

 

Bill Satzer (bsatzer@gmail.com), now retired from 3M Company, spent most of his career as a mathematician working in industry on a variety of applications. He did his PhD work in dynamical systems and celestial mechanics.