Original title:
Vícekriteriální metody dělení grafů
Translated title:
Multicriteria graph partitioning
Authors:
Houška, Ondřej ; Tůma, Miroslav (advisor) ; Hnětynková, Iveta (referee) Document type: Bachelor's theses
Year:
2020
Language:
cze Abstract:
[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
Keywords:
Conjugate Gradient method; graph partitioning; parallel computations; solving linear systems; sparse matrices; dělení grafů; metoda konjugovaných gradientů; paralelní výpočty; řešení soustav rovnic; řídké matice
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/121232