101.770 VO (3std Vorlesung, Sommersemester 2019)
Iterative solution of large systems of equations
TISS-Homepage

Date and location

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

#DateTopicLecturer
106.03.2019Introduction, sparse matricesFaustmann
207.03.2019Direct solvers, ordering strategiesFaustmann
313.03.2019Basic iterative methodsFaustmann
414.03.2019Basic methods - SPD caseFaustmann
520.03.2019Convergence Jacobi, GSFaustmann
621.03.2019Young's theoremFaustmann
727.03.2019Chebyshev accelerationFaustmann
828.03.2019Gradient MethodsRieder
903.04.2019The CG-MethodRieder
1004.04.2019Convergence of CG methodRieder
1110.04.2019The Arnoldi and Lanczos processesRieder
1211.04.2019The D-Lanczos methodRieder
1302.05.2019General Krylov methodsRieder
1408.05.2019GMRESRieder
1515.05.2019Methods based on biorthognalizationRieder
1616.05.2019BiCGRieder
1722.05.2019Preconditioning - in generalFaustmann
1823.05.2019Incomplete LUFaustmann
1929.05.2019Polynomial preconditioners, FEMFaustmann
2005.06.2019Error smoothing, The two grid methodFaustmann
2106.06.2019Convergence of TG methodFaustmann
2212.06.2019MultigridFaustmann
2313.06.2019Full multigridFaustmann
2419.06.2019Additive Schwarz preconditioningFaustmann
2526.06.2019Domain decompositionFaustmann

Exercises

The exercise sheets can be found here one week before the exercise takes place.

#Online sinceExercise sheet, discussed on
107.03.2019First exercise sheet- discussed on 14.3.[link]
214.03.2019Second exercise sheet- discussed on 21.3.[link]
320.03.2019Third exercise sheet- discussed on 4.4.[link]
427.03.2019Fourth exercise sheet- discussed on 11.4.[link]
525.04.2019Fifth exercise sheet- discussed on 2.5.[link]
603.05.2019Sixth exercise sheet- discussed on 16.5.[link]
716.05.2019Seventh exercise sheet- discussed on 23.5.[link]
823.05.2019Eighth exercise sheet- discussed on 6.6.[link]
906.06.2019Nineth 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

Examination modalities

Oral examination, make an appointment by e-mail.