Název:
Vícekriteriální metody dělení grafů
Překlad názvu:
Multicriteria graph partitioning
Autoři:
Houška, Ondřej ; Tůma, Miroslav (vedoucí práce) ; Hnětynková, Iveta (oponent) Typ dokumentu: Bakalářské práce
Rok:
2020
Jazyk:
cze
Abstrakt: [cze][eng] Práce se zabývá dělením grafů a aplikací dělení grafů v paralelních algoritmech pro řešení velkých soustav lineárních rovnic s řídkou maticí. Problém dělení grafů je důkladně vyložen a jsou zde popsány standardní metody dělení grafů. Aplikační část se zaměřuje především na předpodmíněnou metodu sdružených gradientů. Jako předpodmínění se používá varianta neúplné Choleského faktorizace založená na odvrhovacím parametru. V práci je vysvětlena role dělení grafů v paralelní variantě této metody a zabývám se v ní vyvažováním zátěže na jednotlivých procesorech. 1The thesis is about graph partitioning and applications of graph partitioning in paral- lel algorithms for solving big sparse linear equations. The problem of graph partitioning is thorougly described and standard graph partitioning algorithms are explained. The appli- cation part is focusing on the Conjugate Gradient method preconditioned by a variant of incomplete Cholesky factorization based on drop tolerance. The role of graph partitioning in the problem decomposition is described and a load balancing problem is studied. 1
Klíčová slova:
dělení grafů; metoda konjugovaných gradientů; paralelní výpočty; řešení soustav rovnic; řídké matice; Conjugate Gradient method; graph partitioning; parallel computations; solving linear systems; sparse matrices