A Parallel Algebraic Multigrid Method for Elliptic Problems with Highly Discontinuous Coefficients

The aim of this thesis is the development of a parallel algebraic multigrid method suitable for solving linear systems arising from the discretization of scalar and systems of partial differential equations. Among others it is suitable from conforming finite element methods, finite volume methods, and discontinuous Galerkin methods. The method is especially tailored for the solution of diffusion problems with highly oscillating and discon- tinuous diffusion coefficients. The presented approach uses a new strength of connection measure for guiding the construction of the coarse level matrices. It uses a heuristic greedy aggregation algorithm that allows for aggressive coarsening. It is able to detect weak connections in the matrix graph even for anisotropic diffusion with bi- and trilinear finite elements and thus leads to semi- coarsening even for these cases. At the same time it keeps the stencil size from the finer levels and thus the total operator complexity low even for three dimensional problems. This leads to a very low memory consump- tion of our solver compared with other methods. We develop extensions of the solver to systems of partial differential equation by using special blocking approaches of the unknowns. These blockings are emulated by the underlying matrix and vector data struc- tures. As the blocking is already available to the compiler, it can be exploited to produce automatically more efficient code. For the solution of the linear systems stemming from Discontinuous Galerkin discretizations, we employ the subspace of continuous linear basis function as the space associated with the first coarse level. The further coarsening is done by using the above algorithm. For the method of Baumann and Oden we need to use overlapping Schwarz methods as smoothers to get a convergent method. Their local subspaces are con- structed using our aggregation algorithm on the blocks consisting of all unknowns associated with each element. Finally we present a parallelisation approach for iterative solvers and use it to parallelise our algebraic multigrid method. In our approach the information about the data decomposition is kept apart from the linear al- gebra solvers and data structures. It is used to keep the data stored in the local memory of the process consistent. Using our proposed consistency model, the efficient sequential linear algebra solvers and data structures can be reused without the need to rewrite the actual solver algorithms