Algorithms for matrix iterative methods 2025/2026

Course Journal

Last update: 18/12/25

Lab 1 - 29/09/2025

Introduction to MatLab, Krylov subspace methods, matrix computation problems

Lab1: ex 1-4

Lecture 1 - 02/10/2025

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

[SB] Chapter 1

From the Gram-Schmidt process to the Arnoldi and Lanczos algorithms. Refer to:

[SB] Section 6.3
[SB] Section 6.6

Lab 2 - 06/10/2025

Arnoldi and Lanczos algorithm, implementation, comparison, and loss of orthogonality.

Lab2: ex 1-3

Lecture 2 - 09/10/2025

Projection methods. Orthogonal and oblique projection methods, well-defined methods, and the 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 - 03/10/2025

Projection methods.

Lab3: ex 1.1-1.3

Lecture 3 - 16/10/2025

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

[SB] Sections 6.7.1.

Lab 4 - 20/10/2025

CG convergence behavior. D-Lanczos.

Lab3: ex 1.1-1.3, 2.

Lecture 4 - 23/10/2025

SYMMLQ and MINRES methods. Refer to:

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

Lab 5 - 27/10/2025

SYMMLQ, MINRES, CG, and the saddle point problem.

Lab5: ex 1.1-1.3.

Lecture 5 - 29/10/2025

CG convergence behavior in exact arithmetic. Refer to:

[LSB] Section 5.6.2-5.6.4

Lanczos algorithm and orthogonal polynomials. Refer to:

[SB] Section 6.6.

Lab 6 - 3/11/2025

CG, the moment problem, and the loss of orthogonality.

Lab6: ex 1.1-1.3.

Lecture 6 - 6/11/2025

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

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

Lab 7 - 10/11/2025

CG convergence in finite precision arithmetic.

Lab7: ex 1.1-1.3.

Questions about the projects.

Lecture 7 - 13/11/2025

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

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

Lecture 8 - 20/11/2025

GMRES finite precision arithmetic (idea). Arnoldi by QR. GMRES. Givens rotation implementation with QR updates. Refer to:

[LSB] Section 5.10.3. [SB] Section 6.5.3

FOM. Refer to:

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

Nonsymmetric Lanczos

[SB] Sections 6.6.2 and 7.1.

Lab 8 - 24/11/2025

GMRES method.

Exercises:

Lab8.m. Lab 8: Ex 1.1-1.3

Lecture 9 - 27/11/2025

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.

Normal equations and CG. Refer to:

[SB] Section 8.1, 8.3

Lab 9 - 01/12/2025

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 - 04/12/2025

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

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 - 08/12/2025

Lab: Preconditioning techniques for PCG.

Exercises:

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

Lecture 11 - 11/12/2025

PCG and PGMRES

[SB] Sections 9.2 and 9.3

Multigrid as preconditioner (basic ideas)

[SB] 13.2, 13.3

Lab 11 - 15/12/2025

Lab: Lyapunov matrix equation.

Exercises:

Lab11.m, Lab 11: Ex 1.1, 1.2.

Lecture 12 - 18/12/2025

Elements of matrix equations

Refer to:

[https://www.dm.unibo.it/~simoncin/matrixeq.pdf] Section 4

Error norm estimation in CG

Refer to

[https://epubs.siam.org/doi/book/10.1137/1.9781611977868] Chapters 1-4

[https://www.karlin.mff.cuni.cz/~ptichy/download/public/MeTi2012.pdf] Sections 1, 2, 4

Exam:

The exam will cover all the material presented in lectures and practicals throughout the semester and will be conducted in oral form.

In addition, students are required to complete one homework assignment during the semester. The assignment is a team project, in which each team must reproduce, using MATLAB, the experiments described in an assigned research article.

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]
G. Meurant and P. Tichý, Error Norm Estimation in the Conjugate Gradient Algorithm, Society for Industrial and Applied Mathematics, 2024.
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):

Google Sites

Report abuse