Reduced communication algoritms: theory and practice

• Název práce v češtině: Teorie a praxe paralelních algoritmů s omezenou komunikací
• Název v anglickém jazyce: Reduced communication algoritms: theory and practice
• Klíčová slova: Krylovovské metody pro řešení soustav lineárních rovnic, paralelní výpočty, algoritmy s omezenou komunikací
• Klíčová slova anglicky: Krylov space methods, parallel computer architectures, communication avoiding, reduced commmunication
• Akademický rok vypsání: 2015/2016
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra numerické matematiky (32-KNM)
• Vedoucí / školitel: prof. Ing. Miroslav Tůma, CSc.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 05.11.2015
• Datum zadání: 11.11.2015
• Datum potvrzení stud. oddělením: 24.11.2015
• Datum a čas obhajoby: 11.09.2019 09:00
• Datum odevzdání elektronické podoby: 19.07.2019
• Datum odevzdání tištěné podoby: 19.07.2019
• Datum proběhlé obhajoby: 11.09.2019
• Oponenti: doc. Ing. Miroslav Rozložník, Dr.

Zásady pro vypracování

Pokrok posledního desetiletí v konstrukci moderního paralelního výpočetního prostředí s sebou také přinesl
stále naléhavější otázku, jak na nich rychle řešit velmi rozsáhlé algebraické systémy vznikající
například jako výsledek matematického a fyzikálního modelování. Jednou z cest
může být další vývoj algoritmických technik, které se snaží omezovat komunikaci jader, procesorů i počítačů a
nahrazovat ji například dalšími numerickými operacemi. Jinou cestou může být analýza dosud vyvinutých metod.
V posunu celé oblasti vědecko-technických výpočtů, který se týká omezení komunikace v algoritmech, se skrývá řada problémů
se stabilitou numerických výpočtů, které jsou dobře vidět například u Krylovovských metod a také navazujících problémů
týkajících se jejich předpodmiňování. Práce bude mít za úkol získat orientaci
v části tématu věnujícímu se iteračním metodám a jejich předpodmiňování.

Seznam odborné literatury

Erin Carson: Communication-Avoiding Krylov Subspace Methods in Theory and Practice, University of California, Berkeley
Technical Report No. UCB/EECS-2015-179 (2015)

G. Ballard, E. Carson, J. Demmel, M. Hoemmen, N. Knight and O. Schwartz: Communication lower bounds and
optimal algorithms for numerical linear algebra, Acta Numerica 2014, 1-155.


Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM, Philadelpha, PA,
2003.

J. Liesen, Z. Strakoš: Krylov Subspace Methods. Principles and Analysis, Oxford University Press, 2012.

Předběžná náplň práce

Cílem je shrnout současný stav v oblasti numerických algoritmů s omezenou komunikací se zaměřením na iterační metody pro řešení soustav lineárních algebraických rovnic a jejich předpodmínění.

Předběžná náplň práce v anglickém jazyce

The goal is to summarize the state-of-the-art in numerical algorithms with reduced communication, in particular, in the field of iterative methods and their preconditionings.