Metody pro řídké matice

Garant předmětu:

Přednášející:

Cvičící:

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:

Základní kurzy matematické analýzy, lineární algebry, numerické matematiky a numerické lineární algebry (dle přednášek na FJFI ČVUT v Praze 01MA1, 01MAA2-4, 01LA1, 01LAA2, 01NM, 01PNLA).

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. Popis struktury řídkých matic a vznik zaplnění při Choleskiho 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:

Znalosti:

Metody pro ukládání řídkých matic v počítači, vznik zaplnění při Choleskiho rozkladu symetrické pozitivně definitní matice, eliminační stromy, vliv uspořádání soustavy rovnic, rozšíření na obecnější systémy, iterační metody a předpodmínění, stacionární iterační metody, neúplné LU rozklady, úvod do multigridních metod.

Schopnosti:

Použití výše uvedených metod pro řešení soustav rovnic pocházejících z diskretizací eliptických či parabolických úloh metodou sítí nebo metodou konečných prvků.

Studijní materiály:

Povinná literatura:

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

Doporučená literatura:

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

Studijní pomůcky:

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

Poznámka:

Další informace:

Pro tento předmět se rozvrh nepřipravuje

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

• Matematické inženýrství (volitelný předmět)
• Aplikace softwarového inženýrství (volitelný předmět)