Algorithms for matrix iterative methods

Course Journal

Last update: 25/11/20

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.

  • La[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 Gramm-Schmidt process to Arnoldi algorithm. Refer to:

  • [SB] Sections 6.3.1

Lab: Il-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.


Exam:

Exam dates:

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 iterative methods treated in the course

Scheme MIM 2.pdf

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]

  • 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):