Last update: 31/12/21

Lecture 1 - 29/09/21

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

• [SB] Chapter 1.

Lecture 2 - 29/09/21

Lab: Introduction, definition of matrices, condition number, solving linear systems

Exercises:

• Lab1a.m. Lab 1: Ex 1-4 + bonus track.

Lecture 3 - 06/10/21

Discretization of Partial Differential Equations by Finite Difference Methods and Finite Element Methods. Refer to:

• [SB] Sections 2.1, 2.2.1-2.2.5, 2.3.

Lecture 4 - 06/10/21

Lab: Finite difference method

Exercises:

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

Lecture 5 - 13/10/21

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)

Lecture 6 - 13/10/21

Lab: Stationary iterative methods

Exercises:

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

Lecture 7 - 20/10/21

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

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

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

Lecture 8 - 20/10/21

Lab: Projection methods

Exercises:

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

Lecture 9 - 27/10/21

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

• [SB] Sections 6.3 and 6.6.

Lecture 10 - 27/10/21

Lab: Projection methods

Exercises:

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

Lecture 11 - 03/11/21

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

• [SB] Sections 6.6.2 and 7.1.

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

• [SB] Sections 6.7.1.

Lecture 12 - 03/11/21

Lab: Lanczos algorithm

Exercises:

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

Lecture 13 - 10/11/21

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.

Lecture 14 - 10/11/21

Lab: Conjugate Gradient

Exercises:

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

Lecture 15 - 01/12/21

SYMMLQ and MINRES methods. Refer to:

• SYMMLQ, [LSB] Section 2.5.4.

• MINRES, [LSB] Section 2.5.5.

Non-symmetric case: FOM. Refer to:

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

Lecture 16 - 01/12/21

Lab: CG, SYMMLQ, MINRES methods.

Exercises:

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

Lecture 17 - 08/12/21

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

• [LSB] Section 2.5.5.

  1. • [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: short recurrence. Non-symmetric Lanczos, BiCG and QMR methods. Refer to:

• [SB] Section 7.2-7.3.

Lecture 18 - 08/12/21

Lab: CG, SYMMLQ, MINRES methods.

Exercises:

• Lab8a.m. Lab 8: Ex 1.1-1.3.

Lecture 19 - 15/12/21

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: CGNR (CGLS). Refer to:

• [SB] Section 8.1, 8.3

Lecture 20 - 15/12/21

Lab:Non-symmetric case and short recurrences.

Exercises:

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

Normal Equations and regularization by CGNR

Exercises:

• Lab9b.m. Lab 9: Ex 2.1

Lecture 21 - 22/12/21

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]

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.

Lecture 22 - 22/12/21

Lab: Preconditioning techniques for PCG.

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

Lecture 23 - 05/01/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 24 - 05/01/22

Discussion and questions.