The effect of mesh partitioning quality on the performance of a scientific application in an HPC environment

Abstract

The need of fast and reliable methods to solve large linear systems of equations is growing rapidly. Because this is a challenging problem, several techniques have been developed in order to solve it accurately and efficiently. Geometric Multigrid methods are being used to solve these problems, as they accelerate the convergence to a solution. With these methods, it is possible to use a coarser grid as an input, reducing the problem domain and thus reducing the computational cost. The focus of this thesis is the development of new algorithms to generate a sequence of coarser grids from the original grid. By treating this problem as a minimization problem, one can attempt to optimize the overall grid quality by choosing how to merge elements. In order to evaluate our algorithms, we are going define how to quantify the overall grid quality, and therefore analyse the grids obtained by them. We are also going to use the multilevel grid construction paradigm, which is known to be adequate to solve similar problems. Such construction can be done in parallel, by adding a small overhead and not sacrificing the quality produced by our multilevel constructor. Hence, we can achieve a high level of concurrency.