Direct Methods for Sparse Matrices

Many matrices that occur in computational linear algebra are sparse, meaning that most of the entries in the matrix are zero. Data structures that keep only the nonzero entries in a sparse matrix along with information on the indices of the nonzero entries can substantially reduce the required storage. In many applications, conventional dense matrix storage would exceed the available memory and sparse matrix techniques are absolutely essential. In languages like C and Fortran, sparse matrices are typically handled by specialized software libraries. MATLAB includes data structures and algorithms for sparse matrices, and many users make use of sparse matrices with little understanding of how MATLAB handles sparse matrices internally.

Iterative algorithms for the solution of linear systems of equations are most commonly used to solve large scale sparse systems of linear equations arising from the discretizations of systems of partial differential equations. These iterative methods are commonly introduced in courses on numerical linear algebra. Direct methods for the solution of sparse linear systems of equations by LU or Cholesky factorization are not as well known but have important applications, particularly in linear and nonlinear optimization.

This book on direct factorization methods for sparse systems of equations is an extensively updated and expanded second edition of a classic book on the subject from the 1970s. The book begins with a discussion of sparse storage formats and basic operations on sparse matrices, followed by a review of factorization methods for dense matrices. The authors then discuss LU factorization of sparse matrices, pivoting for numerical stability and sparsity of factors, heuristics for ordering the columns of the matrix, and methods for the solution of systems of equations involving the L and U factors. Specialized methods for matrices arising in finite element methods and parallel algorithms are also discussed.

For the topics that it covers, this book is a well written and authoritative reference that should be of interest to anyone involved in the implementation of sparse LU factorization software. It is less well attuned to the needs of users of sparse factorization software, however, since the book lacks a discussion of the available software packages. As such, I expect that the book will mostly be used as a reference by researchers working in the field rather than as a textbook or guide for users of direct methods for sparse systems.

Furthermore, there are some important topics that the book does not discuss. I would have liked to see more on sparse Cholesky factorization, sparse QR factorization, and methods for least squares problems. Timothy Davis’s Direct Methods for Sparse Linear Systems is a book that discusses these missing topics and provides a broad introduction to direct methods; it would be a better starting point for most readers.

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.