Lecture plan

The lecture plan will be continuously updated.

Date Topics Reading
Introduction and basic iterative methods
Week 34 Introduction
Sparse linear systems
Jacobi and Gauss-Seidel methods
YS, Chapters 4.1, 1.5.
As a preparation for the course, it might make sense to review your linear algebra, on which this course heavily relies.
If you have not heard about finite difference methods for elliptic PDEs before, I would suggest to read through YS, 2.1, 2.2.1-2.2.3, 2.2.5. 1)
Additional information on sparse matrices can be found in YS, 3.1, 3.4-3.6.
Week 36 Jacobi and Gauss-Seidel methods (Theory)
Theory of basic iterative methods
Diagonal dominance
SOR
Red-black Gauss-Seidel method
YS, Chapters 4.2.1, 4.2.3, 4.2.4
In Chapter 12.4, you can in principle find some ideas of red-black coloring, although these might be difficult to understand at the moment. We will get back to this topic later in the course.
Week 37 Fast Poisson solvers
Projections
Basics of projection methods
Steepest descent and MR method
E. Rønquist: Note on The Poisson problem in R2: diagonalization methods
YS, Chapters 1.12, 5.1, 5.2, 5.3
Week 38 Projection methods
Krylov subspace methods
Arnoldi's method
FOM
YS Chapters 5.3, 6.1, 6.2, 6.3, 6.4
The Krylov subspace methods are probably the conceptually most difficult methods discussed in this class. It could be a good idea to look briefly over chapters 6.1 and 6.2 of Saad's book in preparation of the lectures.
Week 39 GMRES
Lanczos and D-Lanczos algorithm
CG method
(brief review of least squares problems)
YS Chapters 6.5.1-6.5.5, 6.6, 6.7
More information about overdetermined linear systems can e.g. be found in Chapter 3.13 of Quarteroni, Sacco and Saleri, Numerical Mathematics.
Week 40 CG method (brief repetition)
Convergence analysis of CG and GMRES
Chebyshev polynomials
Idea of preconditioning
Different examples of preconditioners
YS Chapters 6.7, 6.11, 9.1, 10.1-10.2
Week 41 PCG
Preconditioned GMRES method
Flexible preconditioning
Example of CG and PCG method
Idea of multigrid methods
YS Chapters 9.2-9.4, 13.1
Week 42 Multigrid methods
Discussion of smoothers
Weighted Jacobi method
Intergrid operations
V-cycles and W-cycles
YS Chapters 13.1-13.4
Week 43 Multigrid as a preconditioner
Red-black Gauss-Seidel in multigrid
Basic idea of domain decomposition
Additive and multiplicative Schwarz sweeps
Singular value decomposition (SVD)
YS 12.4.1, 12.4.2, 14.1, 14.3
Note on the singular value decomposition
Week 44 Pseudoinverse
SVD and over-/underdetermined systems
Numerical computation of eigenvalues
Schur decomposition
Basic QR algorithm
Note on the singular value decomposition
TB 25, 28 - copies of these chapters can be found on Blackboard.
Week 45 Reduction of matrices to Hessenberg form
Power iteration
Inverse iteration
Rayleigh quotient iteration
QR algorithm with shifts
TB 25-29 - copies of these chapters can be found on Blackboard.
Week 46 Inverse problems and Regularisation
Truncated SVD
Large eigenvalue problems
Note on the singular value decomposition
The lecture on Tuesday will be held by Adrian Kirkeby
Week 47 Summary
Questions (and answers)
On Tuesday I will provide an overview of the lecture.
Thursday is reserved for questions.

YS refers to the book Iterative Methods for Sparse Linear Systems by Yousef Saad.
TB refers to the book Numerical Linear Algebra by L. N. Trefethen and D. Bau; GvL refers to the book Matrix Computations by G. Golub and C. Van Loan. Scans of the chapters used in the course will be made available on blackboard.

1)
It is not required for this class that you are familiar with finite difference methods, but the typical examples of linear systems we want to solve stem all from these methods. Thus some basic knowledge will definitely help in the course.
2017-11-08, Markus Grasmair