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

• Název práce v češtině: Vícekriteriální metody dělení grafů
• Název v anglickém jazyce: Multicriteria graph partitioning
• Klíčová slova: paralelní výpočty, dělení grafů, řešení soustav rovnic, metoda konjugovaných gradientů, řídké matice
• Klíčová slova anglicky: parallel computations, graph partitioning, solving linear systems, Conjugate Gradient method, sparse matrices
• Akademický rok vypsání: 2019/2020
• Typ práce: bakalářská práce
• Jazyk práce: češ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í: 29.11.2019
• Datum zadání: 03.12.2019
• Datum potvrzení stud. oddělením: 09.12.2019
• Datum a čas obhajoby: 16.09.2020 09:00
• Datum odevzdání elektronické podoby: 30.07.2020
• Datum odevzdání tištěné podoby: 30.07.2020
• Datum proběhlé obhajoby: 16.09.2020
• Oponenti: doc. RNDr. Iveta Hnětynková, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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.

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

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.

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

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