Vícekriteriální metody dělení grafů

• Thesis title in Czech: Vícekriteriální metody dělení grafů
• Thesis title in English: Multicriteria graph partitioning
• Key words: paralelní výpočty, dělení grafů, řešení soustav rovnic, metoda konjugovaných gradientů, řídké matice
• English key words: parallel computations, graph partitioning, solving linear systems, Conjugate Gradient method, sparse matrices
• Academic year of topic announcement: 2019/2020
• Thesis type: Bachelor's thesis
• Thesis language: češ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: 29.11.2019
• Date of assignment: 03.12.2019
• Confirmed by Study dept. on: 09.12.2019
• Date and time of defence: 16.09.2020 09:00
• Date of electronic submission: 30.07.2020
• Date of submission of printed version: 30.07.2020
• Date of proceeded defence: 16.09.2020
• Opponents: doc. RNDr. Iveta Hnětynková, Ph.D.

Guidelines

Problém dělení grafů je základní úlohou spojenou na jedné straně
s urychlováním rešičů soustav lineárních i nelineárních rovnic
a na druhé strane s aplikací pro počítání na moderních paralelních výpočetních architekturách.
Tato práce si dává za úkol se seznámit s metodami dělení grafů se zameřením
na takové metody, které si všímají nejenom řídkosti a struktury matice,
ale i jejích numerických hodnot či případně uvažovaných řešičů. Je totiž zřejmé, že budoucí metody
dělení grafů budou muset ve větší míře než dosud numerické hodnoty
v maticích brát do úvahy.

References

A. Pothen, Graph Partitioning Algorithms With Applications To Scientific Computing, in: Parallel Numerical Algorithms,
1997, 323--368, Kluwer Academic Press

J. W. H. Liu. The role of elimination trees in sparse factorizations. SIAM J. on Matrix Analysis and
Applications, 11(1):134–172, 1990.

I. S. Duff and G. A. Meurant. The effect of ordering on preconditioned conjugate gradients. BIT Numerical
Mathematics, 29:635-657, 1989.

B. Smith, P. Bjørstad, and W. Gropp, Domain Decomposition: Parallel Multilevel Methods
for Elliptic Partial Differential Equations, Cambridge University Press, New York, NY,
USA, 1996.

Preliminary scope of work

Cílem práce je zabývat se metodami řešení soustav rovnic vhodnými pro moderní paralelní počítače se zaměřením na rozdělení řešené úlohy.

Preliminary scope of work in English

The goal is to study methods for solving systems of linear equations for modern parallel computers that strongly depend on appropriate
problem partitioning.