Remaining obstacles to a fully optimal two-dimensional hp-AFEM: near-best conforming hp-partitions, degree-robust broken-to-conforming equivalence, p-robust a posteriori error control, and p-uniform solvers

The hp-adaptive finite element method (hp-AFEM) of Canuto, Nochetto, Stevenson, and Verani (2017) was the first hp-adaptive algorithm with proven convergence and instance optimality for elliptic problems in one and two space dimensions, but its two-dimensional theory retains four explicitly acknowledged gaps: (i) the coarsening routine hp-NEARBEST, built on Binev's tree-approximation algorithm, outputs nonconforming hp-partitions, and enforcing conformity can inflate cardinality without a uniform bound, so no near-best routine over conforming hp-partitions exists; (ii) the comparison between broken (elementwise) and conforming best approximation carries a $(1+\log p)^3$ factor growing with the maximal polynomial degree $p$ (Theorem 4 of that work); (iii) the available residual-based a posteriori error estimator is not discretely efficient with degree-independent constants, so the number of inner REDUCE iterations grows like $\|p\|_\infty^{2+2\varepsilon}$; and (iv) the analysis assumes exact algebraic solves, with no iterative solver of $p$-uniform performance integrated into the cost theory. Later work essentially resolves item (ii) in two dimensions via the p-robust equivalence of continuous and discontinuous piecewise-polynomial best approximation in $H^1$ [10], substantially addresses the algebraic core of item (iv) with an hp-robust multigrid solver [11] although its integration into a complete hp-AFEM convergence and cost theory is only outlined, and resolves item (iii) only conditionally (p-robust contraction under a posteriori verifiable criteria) rather than unconditionally. The surviving open core is item (i) — near-best hp approximation directly over conforming hp-partitions with controlled cardinality — together with the unconditional, degree-robust discrete efficiency and optimality of item (iii) for variable-degree refinement and the integration part of item (iv): wiring $p$-uniform iterative algebraic solvers into the hp-AFEM convergence and cost analysis.

Background

The hp-version of the finite element method (hp-FEM) approximates solutions of elliptic partial differential equations by piecewise polynomials in which both the local mesh size $h$ and the local polynomial degree $p$ vary across the domain; combining mesh refinement ($h$-refinement) with degree enrichment ($p$-enrichment) can yield exponential convergence for piecewise-analytic solutions. An adaptive hp method (hp-AFEM) iterates the standard loop SOLVE–ESTIMATE–MARK–REFINE, and one asks not only for convergence but for (instance) optimality: at every stage, the error attained should be comparable to the best attainable by any hp discretization of the same complexity, where complexity counts the number of degrees of freedom (roughly, the sum of local polynomial-space dimensions over the partition).

Canuto, Nochetto, Stevenson, and Verani constructed such a method for the Poisson problem in one and two space dimensions. Their algorithm alternates two routines. The routine hp-NEARBEST is a coarsening step based on Binev's tree-approximation algorithm for hp-adaptivity: it produces an hp-partition and discrete data whose combined error functional is near-best among all hp-partitions of comparable complexity, but the partition it returns is generally nonconforming, meaning the associated triangulation is not edge-to-edge (triangles may meet along part of an edge). The routine REDUCE is an inner AFEM loop that starts from a conforming partition (one where any two triangles share a full edge, a vertex, or nothing — the structure required by continuous Galerkin discretizations) and refines it, guided by an a posteriori error estimator (a computable quantity bounding the unknown error), until the error is reduced by a fixed factor; newest vertex bisection, which splits a triangle along the segment from its most recently created vertex to the opposite edge midpoint, is the refinement rule that keeps the mesh conforming under $h$-refinement. The paper proves convergence of the combined iteration and instance optimality of the coarsened outputs.

In two dimensions, four obstructions to a fully optimal, cost-controlled theory remain, and the paper states each of them explicitly. First, after a call of hp-NEARBEST the generally nonconforming partition $\mathcal{D}$ must be replaced by its minimal conforming refinement $\mathcal{C}(\mathcal{D})$, and the ratio $\#\mathcal{C}(\mathcal{D})/\#\mathcal{D}$ admits no uniform bound: a large triangle carrying a high polynomial degree surrounded by small degree-1 triangles forces arbitrarily many refinements. Hence no algorithm is known that is near-best directly among conforming hp-partitions. Second, to quantify the reduction factor of REDUCE one must compare the broken (elementwise, discontinuous) best approximation errors $e_D(w)$, which feed the tree algorithm, with the best error from the conforming space $V_\mathcal{D}^c$; the paper's Theorem 4 proves (with $\lesssim$ suppressing a generic multiplicative constant)

$$\inf_{v\in V_\mathcal{D}^c}|w-v|_{H^1(\Omega)}^2 \lesssim \bigl(1+\log\|p_\mathcal{D}\|_\infty\bigr)^3\sum_{D} e_D(w),$$

extending an earlier $h$-version result of Veeser, and asks whether the logarithmic factor can be removed, i.e., whether a $p$-independent equivalence between broken and conforming best errors holds. Third, the residual-based estimator of Melenk and Wohlmuth employed in two dimensions is $p$-sensitive: its discrete efficiency constant (the constant relating the estimator to the error of the discrete, Galerkin solution) decays like $\|p\|_\infty^{-2-2\varepsilon}$, so the number of REDUCE iterations needed for a fixed error reduction grows like $\|p\|_\infty^{2+2\varepsilon}$; an estimator — for instance of the equilibrated-flux type, built from a locally conservative flux reconstruction — that is provably discretely efficient with constants independent of $p$ was posed as an open target. Fourth, the whole analysis assumes the linear systems are solved exactly, and controlling the total computational cost requires iterative algebraic solvers whose contraction is uniform in the polynomial degree, integrated into the convergence and optimality analysis.

Problem Statement

Remove the remaining causes of suboptimality of the two-dimensional hp-AFEM of Canuto, Nochetto, Stevenson, and Verani, as posed at the end of that work (Sect. 5.3(i)–(iii) and Sect. 1.2 of the journal version), so that a single implementable 2D hp-AFEM has provably optimal error and cost. Concretely, the requested objectives are the four items below; item (ii) is essentially settled by later work [10] and is included for context only, so the mandatory objectives for a new solution are item (i), the unconditional part of item (iii), and the integration part of item (iv), as restated at the end of this section:

(i) Construct a routine that, given a target function and tolerance, efficiently computes — as an implementable replacement for the hp-NEARBEST plus minimal-conforming-refinement step inside the hp-AFEM loop, with controlled computational cost — an hp-approximation that is near-best among conforming hp-partitions: its cardinality (sum of local polynomial-space dimensions) must be bounded by a uniform constant times that of the best conforming hp-partition achieving comparable accuracy, thereby controlling the conformity overhead that Binev's near-best algorithm for nonconforming partitions cannot (the minimal conforming refinement of a nonconforming hp-partition has no uniformly bounded cardinality).

(ii) Prove that the best approximation error from the conforming hp space is bounded by the sum of the broken elementwise best approximation errors with a constant independent of the polynomial degrees, removing the $(1+\log\|p_\mathcal{D}\|_\infty)^3$ factor of the source's Theorem 4.

(iii) Construct an a posteriori error estimator for the 2D hp setting that is reliable and discretely efficient with constants independent of the polynomial degrees, so that a REDUCE-type error-reduction loop terminates after a number of iterations independent of $\|p\|_\infty$ (the source's residual-based estimator requires $\mathcal{O}(\|p\|_\infty^{2+2\varepsilon})$ iterations).

(iv) Integrate iterative algebraic solvers whose contraction is uniform in the polynomial degree into the hp-AFEM convergence and cost analysis, replacing the exact-solve assumption.

The four items share one scientific objective: making the total error and total computational cost of the adaptive hp method provably (instance-)optimal in two dimensions. As established by the cited later literature [6–11], item (ii) is now essentially settled by a p-robust equivalence result with stated caveats, item (iii) has only conditional resolutions, and for item (iv) an hp-robust multigrid solver and inexact-solver strategies exist but their integration into a complete hp-AFEM convergence and cost theory has only been outlined; the completion boundary for a new solution is therefore item (i) — near-best hp approximation directly over conforming hp-partitions with controlled cardinality, computed by an efficient implementable routine — together with the unconditional, degree-independent p-robust discrete efficiency, contraction, and optimality of item (iii) for variable-degree hp refinement, and the integration part of item (iv): wiring $p$-uniform iterative algebraic solvers into the hp-AFEM convergence and cost analysis.

References

1. Claudio Canuto, Ricardo H. Nochetto, Rob Stevenson, Marco Verani. Convergence and optimality of hp-AFEM. Numerische Mathematik 135 (2017) 1073–1119. DOI: 10.1007/s00211-016-0826-x (preprint: arXiv:1503.03996). https://doi.org/10.1007/s00211-016-0826-x
2. Peter Binev. Tree Approximation for hp-Adaptivity. SIAM Journal on Numerical Analysis 56 (2018) 3346–3357. DOI: 10.1137/18M1175070. https://doi.org/10.1137/18M1175070
3. Peter Binev, Francesca Fierro, Andreas Veeser. Near-Best Adaptive Approximation on Conforming Meshes. Constructive Approximation 57 (2023) 327–349. DOI: 10.1007/s00365-022-09612-2 (preprint: arXiv:1912.13437). https://doi.org/10.1007/s00365-022-09612-2
4. Claudio Canuto, Ricardo H. Nochetto, Rob Stevenson, Marco Verani. On p-robust saturation for hp-AFEM. Computers & Mathematics with Applications 73 (2017) 2004–2022. DOI: 10.1016/j.camwa.2017.02.035 (preprint: arXiv:1611.04104). https://doi.org/10.1016/j.camwa.2017.02.035
5. Jan Westerdiep. On p-Robust Saturation on Quadrangulations. Computational Methods in Applied Mathematics 20 (2020) 169–186. DOI: 10.1515/cmam-2018-0136. https://doi.org/10.1515/cmam-2018-0136
6. Patrik Daniel, Alexandre Ern, Iain Smears, Martin Vohralík. An adaptive hp-refinement strategy with computable guaranteed bound on the error reduction factor. Computers & Mathematics with Applications 76 (2018) 967–983. DOI: 10.1016/j.camwa.2018.05.034. https://doi.org/10.1016/j.camwa.2018.05.034
7. Patrik Daniel, Alexandre Ern, Martin Vohralík. An adaptive hp-refinement strategy with inexact solvers and computable guaranteed bound on the error reduction factor. Computer Methods in Applied Mechanics and Engineering 359 (2020) 112607. DOI: 10.1016/j.cma.2019.112607. https://doi.org/10.1016/j.cma.2019.112607
8. Patrik Daniel, Martin Vohralík. Guaranteed contraction of adaptive inexact hp-refinement strategies with realistic stopping criteria. ESAIM: Mathematical Modelling and Numerical Analysis 57 (2023) 329–366. DOI: 10.1051/m2an/2022082. https://doi.org/10.1051/m2an/2022082
9. Théophile Chaumont-Frelet, Zhaonan Dong, Gregor Gantner, Martin Vohralík. On p-robust convergence and optimality of adaptive FEM driven by equilibrated-flux estimators. Preprint arXiv:2603.08887 (2026). https://arxiv.org/abs/2603.08887
10. Martin Vohralík. p-robust equivalence of global continuous and local discontinuous approximation, a p-stable local projector, and optimal elementwise hp approximation estimates in H^1. Preprint hal-04436063 (2024; version 3, March 2026). https://inria.hal.science/hal-04436063
11. Michael Innerberger, Ani Mirači, Dirk Praetorius, Julian Streitberger. hp-Robust multigrid solver on locally refined meshes for FEM discretizations of symmetric elliptic PDEs. ESAIM: Mathematical Modelling and Numerical Analysis 58 (2024) 247–272. DOI: 10.1051/m2an/2023104. https://doi.org/10.1051/m2an/2023104
12. Alexandre Ern, Thirupathi Gudi, Iain Smears, Martin Vohralík. Equivalence of local- and global-best approximations, a simple stable local commuting projector, and optimal hp approximation estimates in H(div). IMA Journal of Numerical Analysis 42 (2022) 1023–1049. DOI: 10.1093/imanum/draa103. https://doi.org/10.1093/imanum/draa103
13. Paola Antonietti, Claudio Canuto, Marco Verani. An Adaptive hp–DG–FE Method for Elliptic Problems: Convergence and Optimality in the 1D Case. Communications on Applied Mathematics and Computation 1 (2019) 309–331. DOI: 10.1007/s42967-019-00026-9. https://doi.org/10.1007/s42967-019-00026-9
14. J. M. Melenk, B. I. Wohlmuth. On residual-based a posteriori error estimation in hp-FEM. Advances in Computational Mathematics 15 (2001) 311–331. DOI: 10.1023/A:1014268310921. https://doi.org/10.1023/A:1014268310921
15. Dietrich Braess, Veronika Pillwein, Joachim Schöberl. Equilibrated residual error estimates are p-robust. Computer Methods in Applied Mechanics and Engineering 198 (2009) 1189–1197. DOI: 10.1016/j.cma.2008.12.010. https://doi.org/10.1016/j.cma.2008.12.010
16. Andreas Veeser. Approximating Gradients with Continuous Piecewise Polynomial Functions. Foundations of Computational Mathematics 16 (2016) 723–750. DOI: 10.1007/s10208-015-9262-z. https://doi.org/10.1007/s10208-015-9262-z