GravoTet: A Fast Multigrid Hierarchy
Construction for Tetrahedral Meshes

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 the 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.

Method

GravoTet combines fast point sampling with graph-Voronoi-based coarsening to build a hierarchy of tetrahedral meshes without explicit remeshing. At each level, a set of vertices is sampled using fast disc sampling and then clustered via a two-phase Dijkstra Voronoi computation — first restricted to the boundary graph, then expanded into the full volumetric graph. Cliques in the resulting coarse graph define coarse tetrahedra (or faces, edges, and isolated vertices for lower-dimensional features). Barycentric coordinates of fine vertices within their enclosing simplex give the prolongation weights, with at most four non-zero entries per row.

An overview of our method. The input tetrahedral mesh is sampled and a tetrahedron is constructed using the graph-Voronoi approach (shown in 2D for illustration purposes). The sampling is directed by features and the simplex construction focuses on the surface. The resulting coarser mesh is then used to compute barycentric prolongation weights.

Boundary-Aware Coarsening

Preserving boundary fidelity is critical for multigrid performance on tetrahedral meshes. GravoTet introduces two targeted improvements: first, sharp boundary features are identified by their dihedral-angle sum and used to prioritize vertex sampling, so high-curvature regions on the surface are represented at every hierarchy level. Second, the graph-Voronoi clustering proceeds in two phases — propagation is first restricted to the exterior graph (surface geodesics), then expanded into the interior. Together, these modifications keep coarse meshes geometrically faithful to the input boundary with negligible extra runtime.

The Armadillo input tetrahedral mesh (middle) is coarsened using our graph-Voronoi-based approach. We compare the boundary-aware result (right) with the result without boundary awareness (left).

A comparison of the mesh hierarchy produced by applying our boundary-aware approach vs. omitting it for the first three levels of the fidelity mesh.

Comparisons

We benchmark GravoTet against Shi06 (graph-based geometric multigrid), AMG-RS and AMG-SA (algebraic multigrid via PyAMG), and the sparse direct solver CHOLMOD. All multigrid methods share the same V-cycle implementation and differ only in their prolongation operators. Each row below shows the input mesh, then relative residual vs. wall-clock time (convergence) and total execution time breakdown for the Poisson problem, followed by the same two plots for the biharmonic problem. The biharmonic problem is considerably harder for iterative solvers: competing methods frequently hit the time budget, while GravoTet converges on all models. More graphs are provided in the supplementary material.

Armadillo
519k vertices

Spot
709k vertices

Cow
2.0M vertices

Fertility
2.8M vertices

Performance Table

Detailed performance metrics for all 26 comparison models across Poisson and biharmonic problems. Build, Solve, and Total times are in seconds. Bold values mark the best result per row. GravoTet consistently achieves the lowest iteration count and the lowest total time in most cases. On the ill-conditioned biharmonic problem, competing methods frequently hit the time budget while GravoTet converges on every model; CHOLMOD fails on memory for the larger meshes.

Hierarchy Sparsity

Comparative analysis of matrix sparsity showing the average and maximal number of non-zero entries per row in the prolongation matrices, alongside the resulting iteration counts. GravoTet's graph-Voronoi construction guarantees at most 4 non-zero entries per row, keeping the prolongation operators extremely sparse while consistently requiring fewer iterations than competing methods for both Poisson and biharmonic problems.

Quick Summary

• Extends the graph-Voronoi multigrid idea of Gravo MG from surfaces to volumetric tetrahedral meshes
• Builds the entire hierarchy from fast point sampling and graph-Voronoi clustering, with no remeshing
• Boundary-aware coarsening: feature-prioritized sampling and exterior-first clustering preserve the domain boundary
• Barycentric prolongation weights with at most four nonzero entries per row keep the operators extremely sparse
• Faster than competing geometric multigrid, algebraic multigrid (AMG-RS, AMG-SA) and the direct solver CHOLMOD on large Poisson and biharmonic problems

BibTeX

Citation coming soon.