- publication
- SMI 2026
- authors
- Marcel Padilla, Ruben Wiersma, Tim Huisman, Jackson Campolattaro, Olga Sorkine-Hornung, Klaus Hildebrandt
GravoTet is a fast, boundary-aware multigrid hierarchy construction method for tetrahedral meshes. The hierarchy yields barycentric prolongation and restriction operators that accelerate the solution of volumetric Poisson and biharmonic problems, achieving faster convergence in V-cycle iterations and lower total computation times than a state-of-the-art multigrid and sparse direct solvers.
abstract
Geometric multigrid (GMG) methods are a fundamental tool for efficiently solving large sparse linear systems. A requirement for GMG is a hierarchy of grids; however, many practical volumetric domains are available only as single, irregular tetrahedral meshes, making the construction of a multigrid hierarchy necessary. Existing approaches often trade off speed against hierarchy quality: remeshing- or coarsening-based methods can be expensive to construct, whereas graph-based techniques are fast but often yield weaker multigrid performance. We introduce GravoTet, which bridges this gap by combining geometric structure with graph-based efficiency to construct fast and effective multigrid hierarchies. GravoTet builds a vertex hierarchy and then generates graph-Voronoi diagrams whose dual cells define coarse tetrahedra, enabling rapid construction of multigrid levels. Boundary elements are explicitly prioritized during both sampling and tet generation to preserve boundary. In our evaluation, we solve Poisson and biharmonic problems on irregular tetrahedral meshes and compare GravoTet against state-of-the-art geometric multigrid, algebraic multigrid and direct solvers, demonstrating superior performance, particularly on large meshes.
downloads
acknowledgments
Marcel Padilla was supported by the Alexander von Humboldt Feodor Lynen Fellowship and Jackson Campolattaro by the Dutch Research Council (NWO) under file number OCENW.M.21.346.