Algorithms for matrix iterative methods 2024/2025

Course Journal

Last update: 16/01/25

Lab 1 - 01/10/2024

Introduction and introduction to Matlab.

Lab1: ex 1.1, 1.2

Lecture 1 - 02/10/2024

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

[SB] Chapter 1.

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)

Lab 2 - 08/10/2024

Introduction and introduction to Matlab.

Lab1: ex 1.3, 1.4
Lab1a.m (solutions)

Lab: Stationary iterative methods

Lab 2: Ex 1.1.

Lecture 2 - 09/10/2024

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 - 15/10/2024

Lab: Stationary iterative methods

Lab 2: Ex 1.2-1.3.

Lab: Projection methods

Exercises:

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

Lab 4 - 22/10/2024

Lab: Arnoldi algorithm

Lab4a.m and Lab4b.m,´. Lab 4: Ex 1.1-1.2, 2.1

Lecture 3 - 23/10/2024

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

[SB] Sections 6.1-6.2.
[SB] Sections 6.3.
Lab3.m, proj_sd.m. Lab 3: Ex 1.1-1.3.

Lab 5 - 29/10/2024

Lab: Arnoldi algorithm and Lanczos algorithm.

Lab4a.m and Lab4b.m,´. Lab 4: Ex 2.2, 2.3

Exercises:

Lab5a.m, Lab 5: Ex 1.1-1.2

Lecture 4 - 30/10/2024

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 5 - 6/11/2024

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

[SB] Sections 6.7.1.

Lab 6 - 12/11/2024

Lab: Arnoldi algorithm, Lanczos algorithm, and CG.

Exercises:

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

Lecture 6 - 13/11/2024

SYMMLQ and MINRES methods. Refer to:

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

Lab 7 - 19/11/2024

Lab: CG, SYMMLQ, MINRES methods.

Exercises:

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

Lecture 7 - 20/11/2024

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 8 - 26/11/2024

CG, MINRES, and GMRES on symmetric systems.

Lab7a.m. Lab 7: Ex 1.1-1.3

Lecture 8 - 27/11/2024

Vorobyev problem of moments, matching moment property. Connections between CG (Lanczos) and Gauss quadrature. Refer to:

[LSB] Chapter 3, pp. 146-148, pp. 136-139 (in particular, Theorem 3.7.1).

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

GMRES [SB] Section 6.5.1, 6.5.3-6.5.5.

Lecture 9 - 4/12/2024

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.

Non-symmetric case: short recurrence. 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 - 10/12/2024

GMRES method.

Exercises:

Lab8.m. Lab 8: Ex 1.1-1.3

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

Exercises:

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

Lecture 10 - 11/12/2024

Normal equations and CG. Refer to:

[SB] Section 8.1, 8.3

CGNR (also known as CGLS) and LSQR. Refer to:

[Björck, Elfving, Strakoš, 1998] Section 1, 2, and 3.
https://doi.org/10.1137/S089547989631202X
See the shared folder for a copy

Lab 10 - 17/12/2024

Lab: Preconditioning techniques for PCG.

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

Lecture 11 - 18/12/2024

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.

07/01/2025

Presentation of the student's projects.

08/01/2025

Presentation of the student's projects.

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

Åke Björck, Tommy Elfving, and Zdenek Strakoš, Stability of Conjugate Gradient and Lanczos Methods for Linear Least Squares Problems. SIAM Journal on Matrix Analysis and Applications 1998 19:3, 720-736. https://doi.org/10.1137/S089547989631202X

Google Sites

Report abuse