Algorithms for matrix iterative methods 2023/2024

Course Journal

Last update: 11/01/24

Lecture 1 - 02/10/23

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

[SB] Chapter 1.

Lab 1 - 5/10/23

Introduction to Matlab.

Lecture 2 - 09/10/23

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 2 - 12/10/23

Lab: Stationary iterative methods

Exercises:

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

Lecture 3 - 16/10/23

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 3 - 19/10/23

Lab: Projection methods

Exercises:

Lab3.m, proj_sd.m. Lab 3: Ex 1.1-1.3.

Lecture 4 - 23/10/23

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

[SB] Sections 6.1-6.2.
[SB] Sections 6.3.

Lab 4 - 26/10/23

Lab: Arnoldi algorithm

Exercises:

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

Lecture 5 - 30/10/23

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.

Lecture 6 - 06/11/23

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

[SB] Sections 6.7.1.

Lab 5 - 08/11/23

Lab: Lanczos algorithm.

Exercises:

Lab5a.m, Lab 5: Ex 1.1-1.3

Lecture 7- 13/11/23

SYMMLQ and MINRES methods. Refer to:

SYMMLQ, [LSB] Section 2.5.4.
MINRES [LSB] Section 2.5.5.

Lab 6 - 16/11/23

Lab: CG, SYMMLQ, MINRES methods.

Exercises:

Lab5b.m. Lab 5: Ex 2.1-2.3.

Exercises:

Lab6a.m. Lab 6: Ex 1.1

Lecture 8- 20/11/23

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

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

Lab 7 - 23/11/23

Lab: CG, SYMMLQ, MINRES methods.

Exercises:

Lab6a.m. Lab 6: Ex 1.2-1.3.

Exercises:

Lab7a.m. Lab 7: Ex 1.1

Lecture 9- 27/11/23

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).

Non-symmetric case: FOM. Refer to:

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

Lab 8 - 30/11/23

GMRES method.

Exercises:

Lab7a.m. Lab 7: Ex 1.2-1.1.3
Lab8.m. Lab 8: Ex 1.1-1.3

Lecture 10 - 04/12/23

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 - 07/12/23

Lab: Non-symmetric case and short recurrences. Normal equations.

Exercises:

Lab9a.m, Lab9b.m. Lab 9: Ex 1.1-1.3, 2.1

Lecture 11 - 11/12/23

Normal equations and CG. 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:

[SB] Sections 9.1-9.2.
Figure 1 ( Figure 2.1 in the preprint) in: T. Gergelits , K-A. Mardal , B. F. Nielsen, and Z. Strakoš, Laplacian Preconditioning of Elliptic PDEs: Localization of the Eigenvalues of the Discretized Operator, SIAM Journal on Numerical Analysis, 57 (2019), pp. 1369–1394. [Preprint]

Lab 10 - 14/12/23

Lab: Preconditioning techniques for PCG.

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

Lecture 12 - 18/12/23

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 11 - 21/12/23

Preparation of the students' projects.

Lab 12 - 04/01/24

Questions and discussion about the students' projects.

Lecture 13 - 08/01/24

Presentation of the students' projects.

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.

Lab 13 - 11/01/24

Presentation of the students' projects.

Final remarks.

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):

T. Gergelits , K-A. Mardal , B. F. Nielsen, and Z. Strakoš, Laplacian Preconditioning of Elliptic PDEs: Localization of the Eigenvalues of the Discretized Operator, SIAM Journal on Numerical Analysis, 57 (2019), pp. 1369–1394. [Preprint]

Google Sites

Report abuse