Název:	Numerické modelování a počítače
Zkratka:	NMP
Typ:	povinně volitelný
Rozsah:	14 týdnů, týdně 2 hodiny přednášek + 2 hodiny seminárních cvičení
Kredity:	5
Způsob ukončení:	zkouška
Katedra:	katedra modelování procesů FM TUL
Přednášející:	Doc. Ing. Miroslav Tůma, CSc.

 
Stručná anotace předmětu:

Kurz seznamuje s podstatou vybraných aplikací grafových modelů ve výpočetní matematice a výpočetní informatice. Důraz bude kladen na vysvětlení interakce strukturálních (grafových) závislostí a moderních numerických postupů v řadě aplikačních problémů. Základním a velmi bohatým zdrojem modelů budou postupy v přímých metodách pro řešení rozsáhlých a řídkých systémů algebraických rovnic a jejich implementacích. Po krátkém teoretickém úvodu do řešení řídkých systémů rovnic se předmět zaměří na praktické metody implementace algoritmů na moderních počítačových systémech. Pozornost bude věnována zvláštnostem implementací pro počítače s možnostmi paralelního zpracování. Kurz vznikl rozsáhlým přepracováním kurzu Implementace numerických metod pro studenty Informačních technologií tak, aby jim přiblížil moderní výpočetní postupy bez nutnosti předchozího teoretického studia metod numerické lineární algebry.

 
Témata přednášek:

Řídké matice a jejich modely v aplikované teorii grafů.
Grafové modely pro symetrické a pozitivně definitní matice.
Eliminační strom a jeho algoritmická konstrukce. Stromové a množinové algoritmy.
Odhady zaplnění pro faktorizované matice. Grafové postupy a uspořádání matic a jeho vliv na efektivnost implementací.
Algoritmus minimálního stupně a jeho implementace.
Implementace pásových a profilových schémat. Vliv počítačové architektury na modely grafů a ohodnocených grafů.
Frontální algoritmus a multifrontální metoda.
Blokové algoritmy. Hledání bloků v ohodnocených grafech.
Řešení systémů se symetrickými a indefinitními maticemi - aplikace prolínání grafových a numerických postupů.
Algoritmy pro řešení nesymetrických systémů. Řídký ortogonální rozklad a řídký problém nejmenších čtverců.
Dělení grafů na části a jejich aplikace pro řešení úloh na paralelních počítačových architekturách.
SVD, řídké matice a webovské vyhledávací systémy.

 
Náplň cvičení:

Datové struktury ohodnocených grafů a úvod do implementace grafových algoritmů. Matlab a numerické algoritmy.
Efektivnost grafových algoritmů v řešení lineárních systémů se symetrickými a positivně definitními maticemi.
Bloky a paralelní počítačové architektury.
Paralelní implementace přímých řešičů (praktické provedení se bude odvíjet od dostupného vybavení laboratoří)
Nepřesné přímé řešiče a jejich důležitost v iteračních metodách. Porovnání přímých a iteračních metod.
Praxe dělení grafů.

 
Literatura:

A. George, J.W.H. Liu: Computer Solution of Large and Sparse Positive-definite Systems, Prentice-Hall, Englewood

I.S. Duff, A.M.Erisman, J.K.Reid: Direct Methods for Sparse Matrices, Clarendon Press, Oxford, 1986.

R.E.Tarjan: Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983.

G.Fox, R. Williams, P. Messina: Parallel Computing Works, Morgan Kaufmann Publishers, 1994.

Y. Saad: Iterative Methods for Sparse Linear Systems, PWS Publishing Company, 1996.

 
Prerekvizity: Diskrétní matematika, Grafové algoritmy

Navazující:    -

 
Datum poslední změny: 31.12.2001