Iterative numerical methods in linear algebra

2022/2023
Programme:
Financial Mathematics, Second cycle
Year:
1 ali 2 year
Semester:
first or second
Kind:
optional
Group:
M4
ECTS:
6
Language:
slovenian, english
Hours per week – 1. or 2. semester:
Lectures
2
Seminar
1
Tutorial
2
Lab
0
Content (Syllabus outline)

In case of large sparse matrices we can not apply direct methods (e.g., Gaussian elimination or QR algorithm) to solve a linear system or compute the eigenvalues, as we run out of time or memory.
Iterative methods for linear sytems. Jacobi, Gauss-Seidel and SOR method. Symmetric SOR with Chebyshev acceleration. Krilov subspace. Lanczos and Arnoldi algorithm, GMRES, MINRES and similar methods. Conjugate gradients. Bi-conjugate gradients. Preconditioning.
Nonlinear systems. Newton-GMRES, Broyden's method, GMRES for least squares.
Iterative methods for eigenvalue problems. Rayleight-Ritz method,methods based on Krilov subspaces, Jacobi-Davidson method. Generalized eigenvalue problem, polynomial eigenvalue problem.

Readings

J. W. Demmel: Uporabna numerična linearna algebra, DMFA-založništvo, Ljubljana, 2000.
R. Barrett, M. W. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. van der Vorst: Templates for the Solution of Linear Systems : Building Blocks for Iterative Methods, SIAM, Philadelphia, 1994.
Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, H. van der Vorst: Templates for the Solution of Algebraic Eigenvalue Problems : A Practical Guide, SIAM, Philadelphia, 2000.
G. H. Golub, C. F. Van Loan: Matrix Computations, 3rd edition, Johns Hopkins Univ. Press, Baltimore, 1996.
C. T. Kelley: Iterative Methods for Linear and Nonlinear Equations, SIAM, Philadelphia, 1995.
H. van der Vorst: Iterative Krylov methods for large linear systems, Cambridge University Press, Cambridge, 2003.
Y. Saad: Iterative methods for sparse linear systems. Second edition, SIAM, Philadelphia, 2011.

Objectives and competences

Students learn iterative numerical methods for linear systems and eigenvalue problems where matrices are sparse. New knowledge complements the content of courses Numerical linear algebra and Introduction to numerical methods. The acquired knowledge is consolidated by homework assignements and solving problems using computer programs.

Intended learning outcomes

Knowledge and understanding: Understanding of basic numerical algorithms for sparse matrices. Being able to numerically solve problems wih large sparse matrices. The ability to choose an appropriate algorithm based on matrix properties. Knowledge of computer programming package Matlab or other similar software for solving such problems.
Application: Economical and accurate numerical computation of linear systems or eigenvalue problems with sparse matrices.
Reflection: Understanding of the theory from the applications.
Transferable skills: The ability to solve mathematical problems using a computer. Understanding the differences between the exact and the numerical computation. The subject enriches constructively the knowledge of linear algebra.

Learning and teaching methods

Lectures, exercises, homeworks, consultations, projects

Assessment

Type (homeworks, examination, oral, coursework, project):
homeworks or project
written exam
oral exam
Grading: 1-5 (fail), 6-10 (pass) (according to the Statute of UL)

Lecturer's references

Bor Plestenjak:
HOCHSTENBACH, Michiel E., MUHIČ, Andrej, PLESTENJAK, Bor. On linearizations of the quadratic two-parameter eigenvalue problem. Linear Algebra and its Applications, ISSN 0024-3795. [Print ed.], 2012, vol. 436, iss. 8, str. 2725-2743. [COBISS-SI-ID 16095065]
MUHIČ, Andrej, PLESTENJAK, Bor. On the quadratic two-parameter eigenvalue problem and its linearization. Linear Algebra and its Applications, ISSN 0024-3795. [Print ed.], 2010, vol. 432, iss. 10, str. 2529-2542. [COBISS-SI-ID 15469913]
HOCHSTENBACH, Michiel E., KOŠIR, Tomaž, PLESTENJAK, Bor. A Jacobi-Davidson type method for the two-parameter eigenvalue problem. SIAM journal on matrix analysis and applications, ISSN 0895-4798, 2005, vol. 26, no. 2, str. 477-497. [COBISS-SI-ID 13613401]