Keywords: GPGPU, unstructured grids, multigrid solvers, sparse matrices, finite elements.

We are convinced that geometric multigrid methods are superior to algebraic multigrid methods, if their components are designed with respect to the underlying finite element discretisation. Such an approach, which we call finite element geometric multigrid (FE-GMG), allows the design and development of numerically optimal solvers. While many multigrid components can be parallelised in a straight forward manner, two components pose severe challenges: Robust and strong smoothers are inherently recursive and sequential, and grid transfer operations (prolongation and restriction) have to be re-formulated for the chosen finite element space and mesh hierarchy. Our approach follows the hardware-oriented numerics paradigm and we aim at simultaneously maximising numerical and computational efficiency.

In this paper, we address the second problem and evaluate an implementation technique for geometric multigrid solvers that is based completely on sequences of sparse matrix-vector multiplications. With no loss in performance and only moderately increased memory requirements, this approach allows us to design a multigrid solver that is oblivious of the spatial dimension of the computational domain, the underlying unstructured discretisation grid, and the chosen finite element space. We are thus the first to assemble competitive geometric multigrid solvers for finite element discretisations on unstructured grids that execute very efficiently on both CPUs and GPUs.

Our numerical evaluation yields that the FE-GMG completely assembled by sequences of sparse matrix-vector kernels is able to exploit the parallelism provided by multicore CPUs and GPUs: We gain a speedup of two to three when doubling the amount of memory controllers of the CPU and yet another factor of four to 14 (eight on average) when switching from a multi-core CPU to the GPU. Additionally we show that the numbering of the degrees of freedom can have a huge impact on the performance, up to a factor of 25 on both architectures.

download the full-text of this paper (PDF, 1 pages, 284 Kb)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)