Fundamentals of Matrix Computations

The typical first course in numerical analysis focuses on methods for numerical differentiation, integration, interpolation, and the solution of nonlinear scalar equations. In many cases, the focus is mostly on algorithms, with little attention paid to proofs of convergence and error bounds. A small portion of the course may be devoted to the solution of linear systems of equations, but numerical linear algebra is often left for later courses.

Numerical linear algebra often makes its first appearance in a graduate-level course on numerical methods for partial differential equations, where linear systems of equations and eigenvalue problems arise from the discretization of PDEs by finite difference or finite element methods. Since the matrices involved in the numerical solution of PDEs are typically large and sparse, such courses tend to focus on iterative methods. However, numerical linear algebra is much more broadly applicable in other areas of scientific computing, statistics, machine learning, and optimization.

Fundamentals of Matrix Computations provides a broad introduction to numerical linear algebra that covers the solution of linear systems of equations by direct and iterative methods, orthogonal factorizations, least squares problems, and methods for the solution of eigenvalue problems. Although the author uses very simple finite difference schemes in some examples, numerical methods for PDEs are not really covered in this book.

The book is written in a conversational style, with many helpful examples that clarify important concepts. For example, the presentation of the condition number of a linear system in the second chapter is much clearer than in many other books. Watkins also presents the implicitly shifted QR algorithm as an algorithm involving orthogonal transformations without explicitly using the QR factorization. He argues that this algorithm should be called Francis’s algorithm since it doesn’t actually depend on QR factorization.

The book also discusses important computational aspects of the subject, including the time complexity of the methods, sparse and banded matrices, row- and column-based methods, and the importance of using cache-friendly blocked algorithms. The reader is encouraged to perform computational experiments. Although the author suggests the use of MATLAB and provides some sample MATLAB code, the text is not tightly linked to MATLAB and could be used with other languages such as Python/Numpy.

The presentation is reasonably rigorous, but proofs are presented in enough detail and with sufficient explanation so that the book is accessible to undergraduate students. Having taught a senior level course using the book, I can highly recommend it for use with students who have a reasonable background in linear algebra, programming, and proof based mathematics at the undergraduate level.

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.