Obsah přednášky:

Kurs podává přehled základních metod pro řešení soustav lineárních algebraických rovnic, jejichž matice soustavy je řídká. První část je věnována přímým metodám pro symetrické a pozitivně definitní matice - Choleskiho rozkladu, vzniku zaplnění, vlivu uspořádání soustavy rovnic na množství zaplnění. Získané poznatky jsou dále aplikovány na řešení obecnějších systémů. Druhá část přednášky je věnována předpodmiňování iteračních metod, což zahrnuje analýzu konvergence stacionárních metod a metody sdružených gradientů, jednoduchá předpodmínění (Richardson, Jacobi, Gauss-Seidel, SOR, SSOR), neúplné LU rozklady (ILU). Poslední část přednášky je věnována multigridním metodám.

Osnova přednášek:

1. Řídké matice a jejich reprezentace v počítači.
2. Výpočet Choleskiho rozkladu symetrických a pozitivně definitních matic.
3-4. Popis struktury řídkých matic a vznik zaplnění při Choleskiho rozkladu.
5-6. Vliv uspořádání na vznik zaplnění, algoritmy RCM, minimálního stupně, vnořených řezů, frontální metoda.
7. Poznámky k obecnějším systémům.
8. Iterační metody a předpodmínění, analýza stacionárních metod, regulární rozklady.
9. Příklady jednoduchých předpodmínění, předpodmiňování metody sdružených gradientů.
10. Neúplné LU rozklady (ILU), barevná uspořádání.
11. Multigridní metody - analýza Richardsonovy iterace na modelovém příkladě.
12. Multigridní metody - nested iterations, metoda na 2 sítích, V-cyklus, W-cyklus, FMG.
13.-14. Demonstrace vybraných metod na počítači.

Literatura:

A. George, J. W. Liu: Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981.
Y. Saad: Iterative Methods for Sparse Linear Systems, Second Edition, SIAM, 2003.
Y. Saad: Iterative Methods for Sparse Linear Systems, First edition.