Math 270 C: Applied Numerical Linear Algebra
MS 6229, MWF, 1-1:50 PM
Professor: Joseph Teran
Office: MS 7619E
Office hours: MW, 2-3

Summary

We will be covering iterative methods for numerical linear algebra problems. Iterative methods are potentially must faster than direct methods in many situations. For example, the solution to a linear system of equations can often be obtained with linear cost and storage for sparse matrices (e.g. those arising from finite difference approximations to partial differential equations etc.). For direct methods like Gaussian elimination and QR factorization it is difficult to avoid quadratic cost and storage. For this reason, iterative methods are often preferred in applications where performance is critical. We will cover some of the most powerful iterative algorithms developed over the past 50 years or so. This subject area is of great interest to me personally. I spend most of my time thinking about how we can solve partial differential equations from continuum mechanics faster and more accurately. In all such efforts, numerical linear algebra for a sparse (usually symmetric) system of equations is one of the most fundamental components of the algorithm. Furthermore, it is rarely sufficient to simply apply a "black box" solver to the linear algebra problems that arise. A novel algorithm (usually a variant of those we discuss in class) must be developed to provide optimal performance and place the algorithms as a whole in the proper context of competing techniques:
For example, consider the following two images below:

The image at the left is generated using a "black box" solver (incomplete Choleksy preconditioned conjugate gradient) and is effectively incapable of truly achieving linear computational cost. The image at the right was generated using a novel preconditioner (a multigrid preconditioner) that we developed specifically for a class of matrices generated in these computational fluid dynamics calculations.

Reading

I will be posting my own notes each week: Otherwise, you may find the following textbooks also helpful:
  • Numerical Linear Algebra, by Trefethen and Bau.
  • Applied Numerical Linear Algebra, by Demmel.
  • Matrix Computations, by Golub and van Loan.

Assignments

There will be three homework assignments with equal weight. The work will require some programming (Matlab will be fine) and there will also be some pen and paper problems.

Code

My sparse matrix class (and other related things): algebra.h