CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2023/2024

# Methods for Sparse Matrices

Code Completion Credits Range
01MRMMI KZ 2 2P+0C
Garant předmětu:
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 2023/2024:
Time-table is not available yet
Time-table for summer semester 2023/2024:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-08-15
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet6479906.html