Sparse Matrix Algorithms and Support Preconditioning

Place and time:

Lectures and exercises will be at room 0.111, Cauerstrasse 6.

Overview:

Support preconditioning is a method for solving large sparse linear systems of equations. The method is based on sophisticated graph algorithms that drop entries from a matrix to make it sparser. The sparsified matrix, called a preconditioner, is then factored into triangular factors and is used to accelerate an iterative linear solver. The behavior of the resulting solver can often be analyzed rigorously; for certain classes of matrices (those that are symmetric and close to diagonal dominance), the number of operations that the solver performs is only linear or almost linear in the number of unknowns. The course will cover the basic ideas of support preconditioning, algorithmic tools that are required for constructing and using them, the theory of support preconditioning, as well as extensions and applications. The course requires familiarity with basic linear algebra (linear systems of equations, eigen-decompositions), but no prior background in numerical linear algebra. We will cover the necessary tools (iterative linear solvers, sparse factorization, etc.) in the course.

Outline:

1. Motivation: resistive circuits, dense factorizations, sparse factorizations, iterative solvers, preconditioners.
2. Sparse Cholesky factorizations, reordering for sparsity, bounding the cost of factorizations using separators.
3. Iterative linear solvers, MINRES and Conjugate Gradients, convergence theory and Chebychev solvers, preconditioning.
4. Symmetric diagonally dominant matrices (Laplacians) the isomorphism between them and weighted/signed graphs. Factor width, gain graphs, and H matrices.
5. Subset preconditioners (those of Vaidya, of Spielman and Teng, and others)
6. Support-tree preconditioners (those of Gremban, Miller, and others); preconditioning in a larger space.
7. Recursive application of support precondioners.
8. Beyond Laplacians I: signed graphs, matroids, and maximum-weight bases.
9. Beyond Laplacians II: element-by-element diagonally-dominant approximations.
10. Beyond Laplacians III: Fretsaw preconditioners, linear elasticity.
11. Accurate iterative solution of highly ill-conditioned linear systems.

Literature