A Geometric Multigrid Approach for Finite Elements: Hierarchical Hybrid Grids (starts at 9:30!)

While multicore architectures are becoming usual on desktop machines, supercomputers are approaching millions of cores. The amount of memory and compute power on current clusters enables us e.g. to obtain a resolution of in excess (10 000)^3 =10^12 degrees of freedom. However, on the downside we are forced to partition our domain into extremely many sub-problems. Portions of the algorithm that do not permit such degrees of parallelism can easily become a bottleneck. The Hierarchical Hybrid Grids (HHG) framework is designed to close the gap between flexibility of Finite Element's (FE) and the performance of geometric Multigrid's (MG) by using a compromise between structured and unstructured grids. A coarse input FE mesh is split into the grid primitives vertices, edges, faces, and volumes. The primitives are then refined in a structured way, resulting in semi-structured meshes. The regularity of the resulting meshes may be exploited in such a way that it is no longer necessary to explicitly assemble the global discretization matrix. It permits an efficient matrix-free implementation. This approach allows to solve elliptic partial differential equations with a very high resolution. The first part of the talk gives an introduction into data structures and algorithms of HHG. We will then address the scalability problems and communication overhead created by the coarsest grids in a multigrid hierarchy. Surprisingly, a careful implementation can result in excellent scalability results, i.e. the coarse grids do not seriously effect overall parallel performance.