SIMAI 2025

R3MG: R-Tree-Based Agglomeration of Polytopal Grids with Applications to Multilevel Methods

  • Feder, Marco (Università di Pisa)
  • Cangiani, Andrea (SISSA)
  • Heltai, Luca (Università di Pisa)
  • Africa, Pasquale (SISSA)

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 FEMs, the generation of these hierarchies is often straightforward, and it is performed in a bottom-up approach, by refinement of an initially coarse grid. For complex geometries, 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 simply generated by merging polygonal and polyhedral elements. However, providing automated and good-quality agglomeration strategies for polygonal and polyhedral elements remains a challenging task. In this talk, we present R3MG (R-tree-Based Multigrid): an automated, robust, and dimension-independent approach that generates nested and balanced hierarchies of agglomerates, starting from arbitrary polygonal and polyhedral grids. By leveraging the spatial indexing properties of R-trees, this technique allows the robust and automated generation of nested hierarchies of polytopal agglomerates, that preserve mesh quality and improve computational efficiency, outperforming traditional graph-based methods like METIS in structured, unstructured, and polytopal grid scenarios. We present applications ranging from the generation of three-dimensional grid hierarchies to the construction of parallel geometric multigrid preconditioners for discontinuous Galerkin methods. Finally, we discuss recent advances on the distributed memory implementation of our methodology, based on the C++ library DEAL.II.