101.770 VO (3std Vorlesung, Sommersemester 2019)
Iterative solution of large systems of equations
TISS-Homepage
Date and location
- Lecture dates: Wed 12:15-13:45
Room: Sem.R. DB gelb 03 (Freihaus, 3rd floor yellow)
Lecture dates: Thu 11:15-12:00Room: Sem.R. DA grün 04 (Freihaus, 4th floor green)
- Exercise dates: Thu 10:05-11:05
Room: Sem.R. DA grün 04 (Freihaus, 4th floor green)
Aim of the lecture
A fundamental tool of numerical computations is the solution of (large) linear systems of equations. Typically, such systems are not solved "directly" (i.e., using Gaussian elimination or one of its many variants) but approximately using an iterative scheme. The most important iterative schemes are presented in the course and their properties will be discussed. Knowledge of a variety of techniques is important to be able to select a good method for a given application.
Subject of course
The course will cover some of the most important techniques for solving iteratively large linear systems of equations. In the first part of the lecture course, rather general methodologies such as the CG- and the GMRES methods will be discussed. The second part of the course will focus on more special methods such as multigrid and domain decomposition methods. These latter methodologies are among the most powerful tools to solve very large systems arising from the discretization of elliptic partial differential equations (e.g., by the FEM). Multigrid, for example, has optimal complexity, i.e., its cost grows linearly with the problem size.
Lectures
| # | Date | Topic | Lecturer |
|---|---|---|---|
| 1 | 06.03.2019 | Introduction, sparse matrices | Faustmann |
| 2 | 07.03.2019 | Direct solvers, ordering strategies | Faustmann |
| 3 | 13.03.2019 | Basic iterative methods | Faustmann |
| 4 | 14.03.2019 | Basic methods - SPD case | Faustmann |
| 5 | 20.03.2019 | Convergence Jacobi, GS | Faustmann |
| 6 | 21.03.2019 | Young's theorem | Faustmann |
| 7 | 27.03.2019 | Chebyshev acceleration | Faustmann |
| 8 | 28.03.2019 | Gradient Methods | Rieder |
| 9 | 03.04.2019 | The CG-Method | Rieder |
| 10 | 04.04.2019 | Convergence of CG method | Rieder |
| 11 | 10.04.2019 | The Arnoldi and Lanczos processes | Rieder |
| 12 | 11.04.2019 | The D-Lanczos method | Rieder |
| 13 | 02.05.2019 | General Krylov methods | Rieder |
| 14 | 08.05.2019 | GMRES | Rieder |
| 15 | 15.05.2019 | Methods based on biorthognalization | Rieder |
| 16 | 16.05.2019 | BiCG | Rieder |
| 17 | 22.05.2019 | Preconditioning - in general | Faustmann |
| 18 | 23.05.2019 | Incomplete LU | Faustmann |
| 19 | 29.05.2019 | Polynomial preconditioners, FEM | Faustmann |
| 20 | 05.06.2019 | Error smoothing, The two grid method | Faustmann |
| 21 | 06.06.2019 | Convergence of TG method | Faustmann |
| 22 | 12.06.2019 | Multigrid | Faustmann |
| 23 | 13.06.2019 | Full multigrid | Faustmann |
| 24 | 19.06.2019 | Additive Schwarz preconditioning | Faustmann |
| 25 | 26.06.2019 | Domain decomposition | Faustmann |
Exercises
The exercise sheets can be found here one week before the exercise takes place.
| # | Online since | Exercise sheet, discussed on | |
|---|---|---|---|
| 1 | 07.03.2019 | First exercise sheet- discussed on 14.3. | [link] |
| 2 | 14.03.2019 | Second exercise sheet- discussed on 21.3. | [link] |
| 3 | 20.03.2019 | Third exercise sheet- discussed on 4.4. | [link] |
| 4 | 27.03.2019 | Fourth exercise sheet- discussed on 11.4. | [link] |
| 5 | 25.04.2019 | Fifth exercise sheet- discussed on 2.5. | [link] |
| 6 | 03.05.2019 | Sixth exercise sheet- discussed on 16.5. | [link] |
| 7 | 16.05.2019 | Seventh exercise sheet- discussed on 23.5. | [link] |
| 8 | 23.05.2019 | Eighth exercise sheet- discussed on 6.6. | [link] |
| 9 | 06.06.2019 | Nineth exercise sheet- discussed on 13.6. | [link] |
Literature
W. Auzinger, J.M. Melenk: Iterative Solution of large linear systems, lecture notes summer term 2017 Link
Y. Saad: Iterative Methods for Sparse Linear Systems, second edition Link
W. Hackbusch: Iterative solution of large sparse systems of equations, Springer Link