Methods for Sparse Matrices

The course is not on the list Without time-table
Code Completion Credits Range Language
01MRM ZK 2 2+0 Czech
Garant předmětu:
Department of Mathematics

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.


Basic course of Calculus, Linear Algebra, Numerical Methods and Numerical Linear Algebra (in the extent of the courses 01MA1, 01MAA2-4, 01LA1, 01LAA2, 01NM, 01PNLA held at the FNSPE CTU in Prague).

Syllabus of lectures:

1. Sparse matrices and their representation in a computer.

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

3. Description of structure of sparse matrices and creation of fill-in during the Choleski 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:

Methods of representation of the sparse matrices in a computer, creation of fill-in in the Choleski decomposition of a symmetric positive definite matrix, elimination trees, effect of matrix ordering, more general systems, iterative methods and preconditioning, stationary iterative methods, incomplete LU decomposition, introduction to the multigrid methods.

Skills: Application of the above mentioned methods to solve systems of linear algebraic equations originating from the discretization of elliptic and parabolic problems by the finite difference or finite element methods.

Study materials:

Key references:

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

Recommended references:

[2] A. George, J. W. Liu: Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981.

[3] A. Greenbaum: Iterative Methods for Solving Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia 1997

[4] 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.

Further information:
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2024-05-28
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet12073505.html