R3MG: Automated Grid Agglomeration for Discontinuous Galerkin Multilevel Solvers
Please login to view abstract download link
Generating hierarchies of computational grids is a key step in the efficient numerical solution of partial differential equations. For simple geometries and traditional geometric multigrid methods, hierarchy generation is often straightforward and is performed in a bottom-up fashion by refining an initially coarse grid. For complex and fine meshes, however, the construction of a hierarchy of grids may be hard or impractical. The use of polytopal methods is attractive in this respect since coarse grids can be generated by merging fine-mesh elements into polygonal and polyhedral cells. Nevertheless, providing automated agglomeration strategies that produce consistently good-quality coarse cells remains challenging. In this talk, we present R3MG (R-tree-Based Multigrid): a robust and dimension-independent approach that generates nested and balanced hierarchies of agglomerates, starting from fine meshes. By leveraging the spatial indexing properties of R-trees, this technique enables the efficient and automated construction of hierarchies that preserve mesh quality and improve computational efficiency, outperforming traditional graph-based methods such as METIS on both structured and unstructured grids. We demonstrate the effectiveness of our approach on applications ranging from the construction of three-dimensional grid hierarchies to the design of a novel parallel agglomeration-based preconditioner. The latter exploits the flexibility of discontinuous Galerkin frameworks to accelerate the convergence of iterative solvers for the monodomain model in cardiac electrophysiology, a problem characterized by steep, rapidly evolving action potential wavefronts. Computational efficiency is further enhanced through state-of-the-art matrix-free evaluation kernels. Our numerical results demonstrate parallel scalability and robustness in terms of iteration counts, remaining invariant across MPI process counts and mesh refinement. The implementation is based on the POLY DEAL1 framework, built on the C++ DEAL .II finite element library and using MPI for distributed-memory parallelism.
