R3MG-C: a high-order algebraic-geometric multilevel preconditioner for continuous finite element discretizations

Abstract

Algebraic multigrid (AMG) methods are robust and efficient black-box preconditioners for linear systems arising from low-order discretizations of elliptic partial differential equations, but their performance often deteriorates for high-order methods. We introduce an algebraic-geometric multilevel preconditioner for continuous lagrangian finite element discretizations. The method automatically constructs prolongation operators and a Galerkin hierarchy using only the coordinates of finite element support points, without requiring a prescribed mesh hierarchy or domain decomposition. The support-point are recursively partitioned by an R-tree algorithm based on axis-aligned bounding boxes, producing a hierarchy of agglomerates. In contrast to classical AMG, which typically uses piecewise-constant aggregate coarse spaces, our method embeds local discontinuous polynomial spaces of degree $p^{\prime }>0$, defined on the agglomerate boxes, through continuous nodal interpolation. This yields a high-order extension of the Nicolaides coarse space. A two-level analysis quantifies how the coarse polynomial degree offsets the effects of large agglomerates and high-order fine discretizations, under uniform box-regularity, interpolation-stability, and stable-decomposition assumptions. Numerical experiments in two and three dimensions show that the resulting V-cycle, used as a conjugate-gradient preconditioner, maintains stable iteration counts and remains effective in regimes where standard AMG deteriorates.

45 pages, 5 figures, 33 tables

Topics & keywords