# Matrix Iterative Methods II

# Course Journal

### 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.

## Exam:

**Exam dates:**

04.06.2020 Čtvrtek 14:00-17:00 K433KNM

11.06.2020 Čtvrtek 15:00-17:00 K433KNM

18.06.2020 Čtvrtek 14:00-17:00 K433KNM

25.06.2020 Čtvrtek 14:00-17:00 K433KNM

The exam reflects all the material presented on lectures and practicals during the whole semester. The exam has oral form.

Furthermore, students will complete one homework assignments during the semester. The homework consists of implementing a selected method in the MATLAB environment. Results will be presented by the students in the computer laboratory at the end of the semester.

## A map of the discussed iterative methods for linear systems

## Materials and literature:

**Literature:**

**[SB]**Y. Saad: Iterative methods for sparse linear systems, SIAM, Philadelphia, 2003.**(Main source)**[Library]**[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.

Meurant, G.: Computer solution of large linear systems, Studies in Mathematics and Its Applications, North-Holland, 1999.

Freund, R., Nachtigal, N.: QMR: A quasi-minimal residual method for non-hermitian linear systems. Numer. Math. 60, pp. 315-339, 1991.

Saad, Y., Schultz, M.: GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7, pp. 856-869, 1986.

Paige, C., Saunders, M.: LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Software 8, pp. 43-71, 1982.

Paige, C., Saunders, M.: Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal. 12, pp. 617-629, 1975.

**Material discussed in class (in order of appearance):**

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]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]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]