Last update: 03/01/20

Lecture 1 - 19/02/20

Introduction. Spare matrices and discretization of Partial Differential Equations (Finite Difference Method, Finite Element Method). Refer to:

• [SB] p. 45-55 and Section 2.3

Lecture 2 - 22/02/20

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

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

Lecture 3 - 26/02/20

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

• [SB] Sections 4.1-4.2.

Lab: Jacobi and Gauss Seidel methods. Exercises:

• Lab2a.m Ex 1-2.

Lecture 4 - 28/02/20

Introduction. Stationary iterative methods (SOR and SSOR). Refer to:

• [SB] Sections 4.1-4.2.

Lab: SOR and SSOR methods. Exercises:

• Lab2a.m Ex 3-4.

Lecture 5 - 04/03/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: building a random projection method. Exercises:

• Lab3a.m Ex 1-2.

Lecture 6 - 06/03/20

Krylov subspace methods. Refer to:

• [SB] Section 6.2.

Lab: Building the steepest descent method as a projection method. Il-conditioned Krylov matrices, Exercises:

• Lab3a.m Ex 3.

• Lab3b.m Ex 4-5.

Lecture 7 - 11/03/20

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

• [SB] Sections 6.1-6.3.

Lab: Gram-Schmidt process, modified Gram-Schmidt, and Gram-Schmidt with reorthogonalization. Comparison with Arnoldi.

• Lab4a.m Ex 1-3.

Lecture 8 - 13/03/20

Symmetric and non-symmetric Lanczos algorithms. Refer to:

• [SB] Sections 6.6, 7.1.

Lab: Arnoldi with classical Gram-Schmidt and Arnoldi with modified Gram-Schmidt. Symmetric case, comparison between Arnoldi and Lanczos

• Lab4b.m Ex 4-6.

Lecture 9 - 18/03/20

Symmetric linear systems. Conjugate Gradient method (CG), its mathematical characterization and elements of its convergence behavior in exact and in finite precision arithmetic. Derivation of CG from Lanczos algorithm by D-Lanczos method. Refer to:

• [SB] Sections 6.7.1.

• [LSB] Theorem 2.3.1 and Figure 5.19.

Lecture 10 - 21/03/20

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 11 - 25/03/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 12 - 27/03/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.

• [SB] Section 6.5.7 (without proofs) .

Lab: GMRES methods.

• Lab6a.m Ex 1-2.

Lecture 13 - 01/04/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).

• [LSB] Section 5.10.

Lab: GMRES methods.

• Lab6b.m Ex 3-5.

Lecture 14 - 03/04/20

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

• [SB] Section 7.1-7.3.

Lecture 15 - 08/04/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.

Lecture 16 - 15/04/20

Faber-Manteuffel Theorem. Normal equations and CG: CGNR (CGLS). Refer to:

• [SB] Section 6.10.

• [SB] Section 8.1, 8.3.1.

Lab: Short recurrence non-symmetric methods.

• Lab8a.m Ex 1.

Lecture 17 - 17/04/20

Normal equations and CG: CGNE. Refer to:

• [SB] Section 8.3.2.

Lab: Short recurrence non-symmetric methods.

• Lab8c.m Ex 3-4.

Lecture 18 - 22/04/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]

Block Krylov subspaces: Block Arnoldi. Refer to:

• [SB] Section 6.12.

• Section 2.1, Theorem 3.2 (without proofs): A. Frommer, K. Lund, and D.B. Szyld. Block Krylov subspace methods for functions of matrices II: Modified block FOM, accepted for publication in SIMAX (2020). [Preprint]

Lecture 19 - 24/04/20

Lab: Block Arnoldi with MGS.

• Lab9a.m Ex 1,2.

Lecture 20 - 29/04/20

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 21 - 06/05/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.

Lecture 22 - 13/05/20

Lab: Preconditioning techniques for PCG and BiCG.

• Lab10a.m Ex 1-3.

• Lab10b.m Ex 4, 5.

Lecture 23 - 15/05/20

Multigrid: 1D Poisson example, high and low frequencies, fine and coarse grids, prolongation and restriction. Refer to:

• [SB] Sections 13.1, 13.2 (excluding 13.2.2 and 13.2.3), 13.3.

Lecture 24 - 20/05/20

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: Multigrid: basic ideas.

• Lab11a.m Ex 1-2.

Lecture 25 - 22/05/20

Questions, discussion, preparation for the exam.