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ý![]() |
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. |