Reduced communication algoritms: theory and practice

• Thesis title in Czech: Teorie a praxe paralelních algoritmů s omezenou komunikací
• Thesis title in English: Reduced communication algoritms: theory and practice
• Key words: Krylovovské metody pro řešení soustav lineárních rovnic, paralelní výpočty, algoritmy s omezenou komunikací
• English key words: Krylov space methods, parallel computer architectures, communication avoiding, reduced commmunication
• Academic year of topic announcement: 2015/2016
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Numerical Mathematics (32-KNM)
• Supervisor: prof. Ing. Miroslav Tůma, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 05.11.2015
• Date of assignment: 11.11.2015
• Confirmed by Study dept. on: 24.11.2015
• Date and time of defence: 11.09.2019 09:00
• Date of electronic submission: 19.07.2019
• Date of submission of printed version: 19.07.2019
• Date of proceeded defence: 11.09.2019
• Opponents: doc. Ing. Miroslav Rozložník, Dr.

Guidelines

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

References

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.

Preliminary scope of work

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

Preliminary scope of work in English

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.