You are here

Iterative Methods for Sparse Linear Systems

Yousef Saad
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Brian Borchers
, on

Computational methods for linear algebra problems are very important in many areas of engineering and science. In particular, very large linear systems of equations with hundreds of thousands to millions of variables frequently arise in the numerical solution of partial differential equations. These systems of equations are typically sparse, in the sense that nearly all of the coefficients are zero. Saad’s book focuses on iterative methods for the solution of large sparse systems of equations that typically arise in the solution of partial differential equations.

The book begins with three introductory chapters that provide background in linear algebra, discretization of partial differential equations, and sparse matrices. The first chapter on linear algebra contains material that should mostly be familiar to students in mathematics, but the material on normal matrices and M-matrices may be new to many readers. The chapter on discretization of partial differential equations briefly introduces finite difference and finite element methods. Many readers will be unfamiliar with data structures and basic operations on sparse matrices and the chapter on sparse matrices provides a useful introduction.

The main section of the book begins with classical iterative methods including the Jacobi, Gauss-Seidel, successive over-relaxation, and steepest descent methods. The methods are presented in pseudo-code and their convergence is analyzed. Saad then introduces the Krylov subspace concept and modern Krylov subspace methods including conjugate gradients, the generalized minimum residual method, and the quasi-minimal residual method. Linear least squares problems are addressed by applying iterative methods to the normal equations.

The remainder of the book focuses on practical issues in the implementation of iterative methods. The convergence of all of these iterative methods depends critically on the spectrum of the matrix. For nearly singular systems of equations the convergence can be very slow. Performance can be greatly improved by applying an approximate inverse to the system of equations to precondition the system of equations. Chapters 9 and 10 discuss preconditioning techniques including the Jacobi and Gauss-Seidel preconditioners, incomplete LU factorization, and block preconditioners. Chapters 11 and 12 discuss the parallel implementation of iterative methods on shared and distributed memory parallel computers and the parallel implementation of preconditioners. Chapter 13 introduces multi-grid methods, which are specialized methods for elliptic partial differential equations that obtain rapid convergence by exploiting the special structure of these problems. Chapter 14 introduces domain decomposition methods.

This book was written for readers with with varying backgrounds in mathematics, computer science, and engineering. The mathematical presentation is reasonably rigorous but not so abstract that it would be inaccessible to readers with computer science and engineering backgrounds. Algorithms are given with sufficient detail to be easily implemented. There are extensive exercises at the end of each chapter. Computational examples are taken from the Sparsekit and Harwell-Boeing library. Saad’s book provides an accessible overview of a range of classical and modern iterative methods for linear systems of equations. It is recommended for use as a graduate level textbook and reference for readers with backgrounds in mathematics, computer science, and engineering.

Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.

Preface to the Second Edition
Preface to the First Edition

Chapter 1: Background in Linear Algebra
Chapter 2: Discretization of Partial Differential Equations
Chapter 3: Sparse Matrices
Chapter 4: Basic Iterative Methods
Chapter 5: Projection Methods
Chapter 6: Krylov Subspace Methods, Part I
Chapter 7: Krylov Subspace Methods, Part II
Chapter 8: Methods Related to the Normal Equations
Chapter 9: Preconditioned Iterations
Chapter 10: Preconditioning Techniques
Chapter 11: Parallel Implementations
Chapter 12: Parallel Preconditioners
Chapter 13: Multigrid Methods
Chapter 14: Domain Decomposition Methods