Metody pro řídké matice

Garant předmětu:

Jiří Mikyška

Přednášející:

Jiří Mikyška

Cvičící:

Jiří Mikyška

Předmět zajišťuje:

katedra matematiky

Anotace:

Kurz je zaměřen na použití řídkých matic v přímých metodách pro řešení rozsáhlých systémů lineárních algebraických

rovnic. Detailně bude především zpracována teorie rozkladu symetrických a pozitivně definitních matic. Teoretické

výsledky jsou dále aplikovány na řešení obecnějších systémů. Hlavní rysy praktických implementací budou probrány.

Požadavky:

Osnova přednášek:

Osnova:

1. Řídké matice a jejich reprezentace v počítači.

2. Výpočet Choleského rozkladu symetrických a pozitivně definitních matic.

3. Popis struktury řídkých matic a vznik zaplnění při Choleského rozkladu.

4. Vliv uspořádání na vznik zaplnění, algoritmy RCM, minimálního stupně, vnořených řezů, frontální metoda.

5. Poznámky k obecnějším systémům.

6. Iterační metody a předpodmínění, analýza stacionárních metod, regulární rozklady.

7. Příklady jednoduchých předpodmínění, předpodmiňování metody sdružených gradientů.

8. Neúplné LU rozklady (ILU), barevná uspořádání.

9. Multigridní metody - analýza Richardsonovy iterace na modelovém příkladě.

10. Multigridní metody - nested iterations, metoda na 2 sítích, V-cyklus, W-cyklus, FMG.

11. Demonstrace vybraných metod na počítači.

Osnova cvičení:

Cíle studia:

Studijní materiály:

Povinná literatura:

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

Doporučená literatura:

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

Studijní pomůcky:

Počítač s OS Linux a programem Octave nebo Matlab.

Poznámka:

Rozvrh na zimní semestr 2023/2024:

Rozvrh není připraven

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Aplikovaná algebra a analýza (volitelný předmět)
• Aplikace informatiky v přírodních vědách (volitelný předmět)
• Matematické inženýrství (povinný předmět programu)
• Matematická informatika (volitelný předmět)