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.