Methods for Sparse Matrices

Code	Completion	Credits	Range
01MRMMI	KZ	2	2P+0C

Course guarantor:

Jiří Mikyška

Lecturer:

Jiří Mikyška

Tutor:

Jiří Mikyška

Supervisor:

Department of Mathematics

Synopsis:

The course is aimed at utilization of sparse matrices in direct methods for solution of large systems of linear algebraic

equations. The course will cover the decomposition theory for symmetric and positive definite matrices. Theoretic

results will be further applied for solution of more general systems. Main features of the methods and common

implementation issues will be covered.

Requirements:

Syllabus of lectures:

Outline:

1. Sparse matrices and their representation in a computer.

2. Algorithm of the Cholesky decomposition for a symmetric and positive definite matrix.

3. Description of structure of sparse matrices and creation of fill-in during the Cholesky decomposition.

4. Influence of the matrix ordering, algorithms RCM, minimum degree, nested dissection, frontal method.

5. More general systems.

6. Iterative methods and preconditioning, analysis of the stationary methods, regular decompositions.

7. Examples of simple preconditioning, preconditioning of the conjugate gradient method.

8. Incomplete LU decomposition (ILU), color ordering.

9. Multigrid methods - analysis of the Richards iteration on a model example.

10. Multigrid methods - nested iterations, methods on 2 meshes, V-cycle, W-cycle, Full Multigrid method.

11. Demonstration of selected methods on computers.

Syllabus of tutorials:

Study Objective:

Study materials:

Key references:

[1] A. George, J.R. Gilbert, J.W.H. Liu: Graph Theory and Sparse Matrix Computations, Springer, 2011.

[2] M.A. Olshanskii, E.E. Tyrtyshnikov: Iterative Methods for Linear Systems, Theory and Applications, SIAM 2014.

[3] W. Hackbusch: Iterative Solution of Large Sparse Systems of Equations, Springer, 2016.

Recommended references:

4] Y. Saad: Iterative Methods for Sparse Linear Systems, Second Edition, SIAM, 2003.

[5] W. Hackbusch: Multi-Grid Methods and Applications, Springer 2003.

[6] W. L. Briggs, Van E. Henson, S. F. McCormick, A Multigrid Tutorial, Second Editon, SIAM, 2000.

Media and tools:

A computer with OS Linux and software Octave or Matlab.

Note:

Time-table for winter semester 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Wed
Thu	roomTR:301 Mikyška J. 12:00–13:50 (lecture parallel1) Trojanova 13
Fri

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans: