Methods for Sparse Matrices
Code  Completion  Credits  Range  Language 

01MRM  ZK  2  2+0  Czech 
 Garant předmětu:
 Lecturer:
 Tutor:
 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:

Basic course of Calculus, Linear Algebra, Numerical Methods and Numerical Linear Algebra (in the extent of the courses 01MA1, 01MAA24, 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 fillin 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, Vcycle, Wcycle, 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 fillin 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, PrenticeHall, 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.
 Note:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans:

 Matematické inženýrství (elective course)
 Aplikace softwarového inženýrství (elective course)