Numerical Linear Algebra and Matrix Factorizations

This introduction to numerical linear algebra is designed for upper level undergraduate and beginning graduate students in mathematics, statistics, physics and engineering. The only stated prerequisites are first year calculus, introductory linear algebra, and some experience with solving mathematical problems on a computer. The author provides a rapid review of linear algebra before beginning his main exposition.

 

Interest in the subject of numerical linear algebra has been growing steadily. It plays an important role, for example, in data science and machine learning, particularly when very large matrices are involved. 

 

The author suggests that students who use the book will develop a core of skills that include analyzing computational problems and developing their own algorithms in at least three primary areas: linear systems of equations, least squares, and eigenvalue problems. But this is not a leisurely trip through the basic topics in these areas. A great deal of detail is presented, and the pace is fast.

 

All the standard matrix factorizations are discussed here. The author tries to motivate each type of factorization and connect it directly to examples of computation likely to be of interest to his readers. The main exposition starts with tridiagonal diagonally dominant matrices, and presents examples of applications (e.g. cubic spline interpolation) to show why these matrices are of special interest. This is characteristic of the author’s approach: make connections between new ideas presented here and other aspects of numerical analysis, and draw the student’s attention to matrices of various special forms.

 

The author’s approach to numerical linear algebra has a strong theoretical flavor. Essentially all the results have detailed proofs. The book demands a good deal of mathematical maturity from the students and a broader awareness of topics that the stated background does not include.

 

The book is designed for a one-semester course. It includes more material than could reasonably be covered in a semester, but the additional topics give the instructors opportunities to shape their own course. For example, to explore matrix analysis more deeply, topics like Givens rotations, Householder transformations, and Gershgorin’s theorem are included. Kronecker products and the Fourier transform appear in a chapter that explores using the fast Fourier transform to solve the two-dimensional Poisson equation. A basic course based on the book might begin with LU and QR factorizations, and then follow with Singular Value Decomposition and least squares, iterative methods for large linear systems, and eigenvalue computations. MATLAB code for most of the algorithms discussed in the book is provided. Many exercises are provided and some of them will challenge even strong students.

 

The author devotes relatively little discussion to stability of algorithms and error analysis. Where these are discussed it is almost in passing, with little emphasis. There are also surprisingly few examples of actual numerical computations.

 

This book was developed as a text for a course at the University of Oslo. In the U.S., the prerequisites that the authors suggest are probably not sufficient, and many students without more background would find it very challenging. It is more suitable for students with a few more advanced courses that include at least some real analysis and introductory numerical analysis.

---

 

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 ranging from speech recognition and network modeling to optics, material science and the odd bit of high performance computing. He did his PhD work in dynamical systems and celestial mechanics.