Algorithms for matrix iterative methods 2022/2023

Course Journal

Last update: 20/01/23

Lab 1 - 30/09/22

Introduction to Matlab.

  • Exercises in A4MIM2223_lab1.pdf

Lecture 1 - 04/10/22

Introduction. Matrix properties (sparsity, structure, spectral information, symmetry). Refer to:

  • [SB] Chapter 1.

Lab 2 - 07/10/22

Lab: Finite difference method

Exercises:

  • Lab2.m. Lab 2: Ex 1.1-1.2.

Lecture 2 - 11/10/22

Stationary iterative methods (Jacobi, Gauss Seidel, SOR). Refer to:

  • [SB] Sections 4.1, 4.2 (excluding 4.1.1, 4.1.2, 4.2.5)

Intro to projection methods.

Lab 3 - 14/10/22

Lab: Stationary iterative methods

Exercises:

  • Lab3.m. Lab 3: Ex 1.1-1.3.

Lecture 3 - 18/10/22

Projection methods. Orthogonal and oblique projection methods, well-defined methods, finite termination property. Refer to:

  • [SB] Sections 5.1-5.2, Sections 6.1-6.2.

  • [LSB] Sections 2.1-2.2, pp. 11-22.

Lab 4 - 21/10/22

Lab: Projection methods

Exercises:

  • Lab4.m, proj_sd.m. Lab 4: Ex 1.1-1.3.

Lecture 4 - 25/10/22

Introduction to Krylov subspace methods. From Gram-Schmidt process to Arnoldi. Refer to:

  • [SB] Sections 6.1-6.2.

  • [SB] Sections 6.3.

Lecture 5 - 01/11/22

Lanczos algorithm and orthogonal polynomials. Non-symmetric Lanczos algorithm (Lanczos biorthogonalization). Refer to:

  • [SB] Secttion 6.6.

  • [SB] Sections 6.6.2 and 7.1.

Lab 5 - 04/11/22

Lab: Arnoldi algorithm

Exercises:

  • Lab5a.m and Lab5b.m,´. Lab 5: Ex 1.1-1.2, 2.1-2.3

Lecture 6 - 08/11/22

Derivation of CG from Lanczos algorithm and D-Lanczos method. Refer to:

  • [SB] Sections 6.7.1.

Lab 6 - 11/11/22

Lab: Lanczos and Arnoldi algorithms.

Exercises:

  • Lab6a.m. Lab 6: Ex 1.1-1.3.

Lecture 7 - 15/11/22

SYMMLQ and MINRES methods. Refer to:

  • SYMMLQ, [LSB] Section 2.5.4.

Lab X - 18/11/22

Replaced with the online matlab tutorial.

Lecture 8 - 22/11/22

Elements of CG convergence behavior in exact and in finite precision arithmetic. Refer to:

  • [LSB] Section 5.6.4 (pp. 275-276) and Figure 5.8 and 5.19.

  • [SB] Section 6.11.3.

Lab 7 - 25/11/22

Lab: CG, SYMMLQ, MINRES methods.

Exercises:

  • Lab6a.m. Lab 6: Ex 2.1-2.3.

Exercises:

  • Lab6a.m. Lab 7: Ex 1.1

Lecture 9 - 29/11/22

Non symmetric case: MINRES and GMRES methods (mathematical characterization, QR implementation). Refer to:

      • MINRES and GMRES [LSB] Section 2.5.5.

      • GMRES [SB] Section 6.5.1, 6.5.3-6.5.5.

GMRES method convergence and finite precision arithmetic. Refer to:

  • [LSB] pp. 285-286, pp. 289-290, Theorem 5.7.8 at p. 300 (without proof).

Lab 8 - 02/12/22

Lab: CG, SYMMLQ, MINRES methods.

Exercises:

  • Lab7.m. Lab 7: Ex 1.2-1.3

  • Lab8a.m. Lab 8: Ex 1.1.

Lecture 10 - 06/12/22

Non-symmetric case: FOM. Refer to:

  • FOM, [SB] Section 6.4.1, [LSB] p. 61.

Non symmetric case: short recurrence. Non-symmetric Lanczos, BiCG and QMR methods. Refer to:

  • [SB] Section 7.2-7.3.

Non symmetric case: short recurrence. Transpose-free variants: CGS, BiCGStab, and (basic ideas of) TFQMR methods. Refer to:

  • [SB] Section 7.4.1-7.4.3.

Faber-Manteuffel Theorem. Refer to:

  • [SB] Section 6.10.

Lab 9 - 09/12/22

Lab: Non-symmetric case and short recurrences.

Exercises:

  • Lab9a.m. Lab 9: Ex 1.1-1.3.

Lecture 11 - 13/12/22

Normal equations and CG: CGNR (CGLS). Refer to:

  • [SB] Section 8.1, 8.3

Preconditioning. Role of the spectrum and condition number. Preconditioned Conjugate Gradient (PCG), split preconditioner CG. Refer to:

Preconditioning techniques. Preconditioning using stationary iterative methods (Jacobi, Gauss-Seidel, SSOR). Preconditioning using the Incomplete LU factorization (ILU(0) and ILU(p)). Refer to:

  • [SB] Sections 10.1-10.2, 10.3.1-10.3.2.

Lab 10 - 16/12/22

Lab: Preconditioning techniques for PCG.

  • Lab10a.m, Lab10b.m, Lab 10: Ex 1.1-1.3, 2.1.

Lecture 12 - 20/11/22

Multigrid: Standard Multigrid techniques: nested iterations, V-cycles, W-cycles, Full Multigrid scheme (FMG). Refer to:

  • [SB] Sections 13.4.1-13.4.3 and first page of 13.4.4.

Lecture 13 - 03/01/23

Questions and discussion about the course topics

Lab 11 - 06/01/23

Questions and discussion about the laboratory project.

Exam:

Exam

The exam reflects all the material presented in lectures and practicals during the whole semester. The exam has an oral form.

Furthermore, students will complete one homework assignment during the semester. The homework consists of implementing a selected method in the MATLAB environment.

A map of iterative methods studied in the course

Scheme MIM 2.pdf

Matlab

Here is a useful summary of Matlab's basic functions.

Here is Matlab Onramp, a 2 hours online introduction with useful exercises.

Materials and literature:

Literature:

  • [SB] Y. Saad: Iterative methods for sparse linear systems, SIAM, Philadelphia, 2003. (Main source) [Library]
    An open free version can be downloaded     here.

  • [LSB] J. Liesen and Z. Strakos, Krylov Subspace Methods, Principles and Analysis, Oxford University Press, 2012, 408p. [Library]

  • Barrert, R., et all: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, 1994.

  • Higham, N.: Accuracy and stability of numerical algorithms, SIAM, Philadelphia, 2002 (2nd ed.).

  • Meurant, G.: Computer solution of large linear systems, Studies in Mathematics and Its Applications, North-Holland, 1999.

Material discussed in class (in order of appearance):