PhD COURSE ON

ITERATIVE METHODS FOR LINEAR SYSTEMS OF EQUATIONS

By Martin van Gijzen

Delft University of Technology, The Netherlands

October 20-24, 2008

Department of Informatics and Mathematical Modelling, DTU, Denmark

DTU Informatics. Graduate School ITMAN

CLICK HERE FOR THE FINAL ASSIGNMENT
Reports should be made individually. They should be handed in no later than December 1.

Course description

The PhD course gives an overview of modern iterative methods for solving large systems of linear equations. Such systems arise in a variety of applications such as image processing, optimization, data mining, medical and geophysical tomography, geodesy and oceanography.

The purpose of the course is to present state-of-the-art methods for such systems, with emphasis on a combination of practical computational aspects and insight into the underlying theory of the methods.

Solution of a geophysical test problems

Course requirements

The participants must have a fundamental knowledge of numerical analysis and linear algebra and must be able to program in Matlab.
Students are expected to read the following paper as preparation for the course:
A Brief Introduction to Krylov Space Methods for Solving Linear Systems (by prof. Martin Gutknecht)

Format of the course

The course consists of lectures, theoretical assignments and computer exercises, running each day from 9 a.m. to 4 p.m.

Overview of the course

Day 1. Introduction to iterative methods

Simple iterative methods (Jacobi, Gauss Seidel, SOR), simple iterative methods for the normal equations (ART, SIRT) and one-dimensional projection methods.
Lecture, Theoretical assignment, MATLAB assignment, MATLAB code.

Day 2. Projection methods (1)

Lanczos based methods for symmetric systems: CG, CR and MINRES. Methods for the normal equations. Convergence theory.
Lecture, Theoretical assignment, MATLAB assignment.

Day 3. Projection methods (2)

Arnoldi-based methods: GMRES and FOM. Convergence theory. Restarted GMRES, GMRESR.
Lecture, Theoretical assignment, MATLAB assignment, MATLAB code: gmres.m, mmread.m.

Day 4. Projection methods (3)

Bi-Lanczos-based methods: BI-CG and QMR, Bi-CGSTAB and CGS. The Induced Dimension Reduction theorem and IDR(s).
Lecture, Theoretical assignment, MATLAB assignment, MATLAB code: ocean.m, ocean.mat, topo.mat.

Day 5. Preconditioning techniques

Simple iterative methods as preconditioners. ILU. Advanced preconditioners: multigrid, domain decomposition methods, saddle-point preconditioning,
Lecture, Theoretical assignment, MATLAB assignment, MATLAB code.

Useful links

The book Iterative methods for sparse linear systems by Yousef Saad gives a wealth of background information.
Another good book is Lecture Notes on Iterative Methods by Henk van der Vorst.
Netlib is an extremely useful collection of mathematical software, papers, and databases.
The book Templates for the Solution of Linear Systems plus MATLAB scripts of the iterative methods can be found here.
The MATRIX MARKET is the classical collection of test matrices.
A large number of sparse test matrices can be found in Tim Davis' matrix collection at the University of Florida.