Last update: 19/01/21

Lecture 1 - 30/09/20

Introduction. Matrix properties (sparsity, structure, spectral information, symmetry), discretization of Partial Differential Equations by Finite Difference Method. Refer to:

• [SB] p. 45-55

Lecture 2 - 30/09/20

Lab: Introduction, definition of matrices, condition number, solving a linear system, banded matrices. Exercises:

• Lab1a.m Ex 1-2, Lab1b.m Ex 3-5.

Lecture 3 - 07/10/20

Finite Element Method. Refer to:

• [SB] Section 2.3.

Lecture 4 - 07/10/20

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

• [SB] p. 103-105, 111-113, 116-119.

Lab: Jacobi and Gauss Seidel methods. Exercises:

• Lab2a.m Ex 1-2.

Lecture 5 - 14/10/20

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

• [SB] Chapter 5, pp. 129-138.

• [LSB] Chapter 2, pp. 11-19

Lab: SOR method and comparison with other stationary iterative methods:

• Lab2a.m Ex 3-4.

Lecture 6 - 14/10/20

Lab: building a random projection method. Exercises:

• Lab3a.m Ex 1.

Lecture 7 - 04/11/20

Krylov subspace methods. Refer to:

• [SB] Section 6.1-6.2.

Lab: Building the steepest descent method as a projection method. Exercises:

• Lab3a.m Ex 2-3.

Lecture 8 - 04/11/20

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

• [SB] Sections 6.3.1

Lab: Ill-conditioned Krylov matrices. Exercises:

• Lab3b.m Ex 4-5.

Lecture 9 - 11/11/20

Arnoldi algorithm. Refer to:

• [SB] Sections 6.3

Lab: Arnoldi, Gram-Schmidt and modified Gram-Schmidt. Exercises:

• Lab4a.m Ex 1-3.

Lecture 10 - 11/11/20

Lanczos algorithms. Refer to:

• [SB] Sections 6.6

Lab: Symmetric case, comparison between Arnoldi, Arnoldi MGS, and Lanczos

• Lab4b.m Ex 4-6.

Lecture 11 - 18/11/20

Non-symmetric Lanczos algorithms. Refer to:

• [SB] Sections 6.6, 7.1.

Symmetric linear systems. Conjugate Gradient method (CG) and its mathematical characterization.

• [LSB] Theorem 2.3.1.

Lecture 12 - 18/11/20

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

• [SB] Sections 6.7.1.

Lab: CG method and its numerical behavior given different spectral distributions.

• Lab5a.m Ex 1-3.

Lecture 13 - 25/11/20

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

• [LSB] Theorem 2.3.1 and Figure 5.19.

SYMMLQ method. Refer to:

• [LSB] Section 2.5.4.

Lab: CG method and its numerical behavior given different spectral distributions.

• Lab5a.m Ex 1-3.

Lecture 14 - 25/11/20

Symmetric case: MINRES method. Non symmetric case: FOM method. Refer to:

• MINRES, [LSB] Section 2.5.5.

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

Lab: CG, SYMMLQ, MINRES methods.

• Lab5b.m Ex 4-5.

Lecture 15 - 02/12/20

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

• [LSB] Section 2.5.5.

• [SB] Section 6.5.1, 6.5.3-6.5.5.

Lab: GMRES methods.

• Lab6a.m Ex 1-2.

Lecture 16 - 02/12/20

Non symmetric case: 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: GMRES methods.

• Lab6b.m Ex 3-5.

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

• [SB] Section 7.2-7.3.

Lecture 17 - 09/12/20

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.

Lab: Short recurrence non-symmetric methods.

• Lab7.m Ex 1-2.

Faber-Manteuffel Theorem. Refer to:

• [SB] Section 6.10.

Lecture 18 - 09/12/20

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

• [SB] Section 8.1, 8.3

Lab: Regularization and CGNR

• Lab8a.m Ex 1.

Lecture 19 - 16/12/20

Normal equations: Golub-Kahan iterative bidiagonalization. Refer to:

• Section 2 of: I. Hnětynková, M. Plešinger, and Z. Strakoš. The regularizing effect of the Golub-Kahan iterative bidiagonalization and revealing the noise level in the data, BIT Numerical Mathematics 49 (2009), pp. 669-696. [Preprint]

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]

Lecture 20 - 16/12/20

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: Preconditioning techniques for PCG.

• Lab10a.m Ex 1-3.

Lecture 21 - 06/01/21

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.