Generalized preconditioned conjugate gradients for adaptive FEM with optimal complexity

arxiv: 2601.14911 · v2 · submitted 2026-01-21 · 🧮 math.NA · cs.NA

Generalized preconditioned conjugate gradients for adaptive FEM with optimal complexity

Paula Hilbert , Ani Mira\c{c}i , Dirk Praetorius This is my paper

Pith reviewed 2026-05-16 12:36 UTC · model grok-4.3

classification 🧮 math.NA cs.NA

keywords adaptive finite element methodsgeneralized PCGmultigrid preconditioneroptimal complexityh-robustnessp-robustnesselliptic problemsinexact solvers

0 comments p. Extension

The pith

Generalized PCG with contractive multigrid as preconditioner achieves optimal complexity for adaptive finite element methods.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that generalized preconditioned conjugate gradient iterations, when driven by a contractive multigrid preconditioner, meet the two requirements needed for optimal-complexity AFEM on second-order elliptic problems. Each solver step must cost linear work in the number of degrees of freedom, and the algebraic error must contract uniformly in the energy norm. Both properties must hold independently of the local mesh size and the polynomial degree, even while the mesh is refined adaptively. The analysis supplies the missing rigorous justification for the adaptive case, where the sequence of meshes is generated by the AFEM itself, and numerical tests confirm that the approach uses less total work than running the same multigrid method as a direct solver.

Core claim

Generalized PCG with an h- and p-robust contractive multigrid preconditioner satisfies the linear-cost and uniform-contraction requirements for optimal-complexity AFEM, with the contraction holding uniformly across the adaptively generated mesh sequence, and numerical experiments show it outperforms AFEM that uses the multigrid method directly as the solver.

What carries the argument

Generalized preconditioned conjugate gradient (GPCG) iteration that accepts a contractive solver directly as preconditioner without symmetrization, so that an h- and p-robust multigrid method can be inserted while preserving the uniform contraction property on adaptive meshes.

If this is right

AFEM convergence rates remain optimal when measured against total computational work rather than degrees of freedom alone.
Each iteration step has linear complexity in the current number of degrees of freedom.
The algebraic error contracts uniformly in the energy norm, independent of local h and p.
The guarantees apply to the concrete sequence of meshes produced by the adaptive algorithm itself.
The method requires fewer total iterations in practice than using the same multigrid as a direct solver.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same construction could be tried with other contractive iterative methods, such as suitably scaled domain-decomposition solvers, provided they satisfy the uniform contraction property.
p-robustness becomes especially useful when adaptive strategies are combined with high-order elements, because the contraction constant does not degrade as the degree increases.
The framework suggests that preconditioners need not be recomputed from scratch at every refinement step; a slowly varying contractive operator may suffice.
Similar linear-cost uniform-contraction arguments could be explored for nonlinear or time-dependent problems once a suitable contractive linearization step is identified.

Load-bearing premise

A multigrid method must exist that contracts the error at a rate independent of both local mesh size and polynomial degree, and that can be used directly as a preconditioner inside generalized PCG.

What would settle it

Run the GPCG iteration on a sequence of adaptively refined meshes for a model elliptic problem and check whether the observed contraction factor stays bounded independently of the refinement level and polynomial degree; growth of the factor would falsify the uniform robustness claim.

read the original abstract

We consider adaptive finite element methods (AFEMs) with inexact algebraic solvers for second-order symmetric linear elliptic diffusion problems. Optimal complexity of AFEM, i.e., optimal convergence rates with respect to the overall computational cost, hinges on two requirements on the solver. First, each solver step is of linear cost with respect to the number of degrees of freedom. Second, each solver step guarantees uniform contraction of the solver error with respect to the PDE-related energy norm. Both properties must be ensured robustly with respect to the local mesh size h (i.e., h-robustness). While existing literature on geometric multigrid methods (MG) or symmetric additive Schwarz preconditioners for the preconditioned conjugate gradient method (PCG) that are appropriately adapted to adaptive mesh-refinement satisfy these requirements, this paper aims to consider more general solvers. Our main focus is on preconditioners stemming from contractive solvers which need not be symmetrized to be used with Krylov methods and which are not only h-robust but also p-robust, i.e., the contraction constant is independent of the polynomial degree p. In particular, we show that generalized PCG (GPCG) with an h- and p-robust contractive MG as a preconditioner satisfies the requirements for optimal-complexity AFEM and that it numerically outperforms AFEM using MG as a solver. While this is certainly known for (quasi-)uniform meshes, the main contribution of the present work is the rigorous analysis of the interplay of the solver with adaptive mesh-refinement. Numerical experiments underline the theoretical findings.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

GPCG with an h- and p-robust MG preconditioner extends optimal AFEM complexity from quasi-uniform to adaptive meshes, with numerics showing it beats plain MG.

read the letter

The paper's core result is that generalized PCG using a contractive multigrid preconditioner that stays h- and p-robust delivers the linear-cost and uniform-contraction properties needed for optimal-complexity AFEM on adaptively refined meshes. This moves the theory beyond the quasi-uniform case that was already known. The proof focuses on showing the solver error contracts uniformly in the energy norm across the sequence of locally refined meshes, and the numerics confirm faster practical performance than running MG as a direct solver. That extension and the p-robustness angle are the actual new pieces. The analysis treats the MG contraction factor as an input that holds uniformly, which is reasonable if the preconditioner literature already covers it, but it does mean the paper does not re-derive the contraction bound for the specific adaptive grading that AFEM produces. If that bound degrades under heavy local refinement or rising p, the optimal-complexity claim would not hold. The numerics are presented as supporting evidence rather than exhaustive, which is fine for this kind of work. Overall the argument is internally consistent once the MG assumption is granted. This is useful reading for anyone building high-order adaptive codes who needs to know which inexact solvers preserve the optimal rate. It is worth sending to a serious referee; the gap it fills is real even if the MG robustness step is imported.

Referee Report

2 major / 1 minor

Summary. The manuscript analyzes generalized preconditioned conjugate gradient (GPCG) methods that employ h- and p-robust contractive multigrid (MG) preconditioners for adaptive finite element methods (AFEM) on second-order symmetric elliptic problems. It claims that this setup delivers linear cost per solver iteration and uniform contraction in the energy norm, thereby guaranteeing optimal complexity AFEM, with the principal theoretical advance being the rigorous treatment of the solver-AFEM interplay on locally refined adaptive meshes (as opposed to quasi-uniform meshes). Numerical experiments are presented to illustrate that GPCG outperforms direct use of the MG solver.

Significance. If the uniform contraction property of the MG preconditioner holds independently of the adaptive refinement history, the work supplies a flexible route to inexact solvers in AFEM that avoids symmetrization while preserving p-robustness and optimal complexity. The analysis of how a contractive (possibly non-symmetric) preconditioner interacts with the adaptive marking and refinement loop constitutes a useful technical contribution to the literature on optimal-complexity AFEM.

major comments (2)

[Abstract] Abstract: the central claim that GPCG with an h- and p-robust contractive MG preconditioner meets the linear-cost and uniform-contraction requirements for optimal-complexity AFEM rests on the assumption that the MG contraction factor remains bounded uniformly away from 1 for the specific sequence of locally refined meshes generated by AFEM; this uniformity is invoked as an external input rather than established by a self-contained argument or explicit reference within the manuscript.
[Theoretical analysis] Theoretical analysis section (the extension from quasi-uniform to adaptive meshes): the proof that the interplay between the GPCG iteration and the AFEM loop preserves uniform contraction must be checked against the precise dependence of the MG contraction constant on the local grading and refinement history; without an explicit bound or a theorem that isolates this dependence, the load-bearing step from the assumed MG property to the overall optimal-complexity result remains incomplete.

minor comments (1)

[Numerical experiments] Numerical experiments: additional quantitative reporting of observed contraction rates of the MG preconditioner on the adaptively generated meshes would help readers verify that the theoretical uniformity assumption is realized in the reported runs.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments highlight the need to clarify the foundational assumption on the multigrid (MG) contraction factor for adaptively refined meshes. We address both major points below and will revise the manuscript to strengthen the presentation of assumptions, references, and the logical structure of the proof.

read point-by-point responses

Referee: [Abstract] the central claim that GPCG with an h- and p-robust contractive MG preconditioner meets the linear-cost and uniform-contraction requirements rests on the assumption that the MG contraction factor remains bounded uniformly away from 1 for the specific sequence of locally refined meshes generated by AFEM; this uniformity is invoked as an external input rather than established by a self-contained argument or explicit reference within the manuscript.

Authors: We agree that the abstract and introduction should make the assumption explicit. The manuscript relies on existing h- and p-robust MG theory for locally refined meshes (e.g., results establishing contraction factors independent of local grading for geometric MG on AFEM hierarchies). The novel contribution is the rigorous GPCG-AFEM interplay analysis under this standard assumption. We will revise the abstract to state the assumption clearly and add a sentence with explicit literature references. revision: yes
Referee: [Theoretical analysis] the proof that the interplay between the GPCG iteration and the AFEM loop preserves uniform contraction must be checked against the precise dependence of the MG contraction constant on the local grading and refinement history; without an explicit bound or a theorem that isolates this dependence, the load-bearing step from the assumed MG property to the overall optimal-complexity result remains incomplete.

Authors: The theoretical analysis (Section 3) assumes the MG preconditioner satisfies a uniform contraction bound independent of the adaptive refinement history, as is standard in the AFEM-MG literature. We will revise the section to isolate this assumption in a dedicated lemma or remark, citing the precise dependence (or independence) on local grading from the referenced MG theory. This will make the logical chain from MG property to optimal-complexity AFEM fully transparent without reproving the MG result itself. revision: yes

Circularity Check

0 steps flagged

MG preconditioner contractivity and h/p-robustness treated as external inputs; GPCG analysis on adaptive meshes extends prior results without self-reduction

full rationale

The paper assumes the existence of an h- and p-robust contractive multigrid preconditioner whose contraction factor is bounded uniformly away from 1 independently of h, p, and the adaptive refinement history. It then proves that generalized PCG using this preconditioner satisfies the linear-cost and uniform-contraction requirements needed for optimal-complexity AFEM, with the technical contribution being the extension of the argument from quasi-uniform to locally refined meshes. No equation or derivation step inside the paper reduces a claimed prediction to a fitted parameter or to a self-citation that itself depends on the target result; the MG properties are imported as given from the literature and the subsequent GPCG analysis is self-contained relative to those inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard assumption that the underlying PDE is a symmetric linear elliptic diffusion problem and on the external existence of suitable h- and p-robust contractive multigrid solvers; no new free parameters or invented entities are introduced.

axioms (2)

domain assumption The PDE is a second-order symmetric linear elliptic diffusion problem.
Explicitly stated as the problem class considered throughout the abstract.
domain assumption There exist h- and p-robust contractive multigrid solvers that can be used as preconditioners.
The paper invokes these solvers as black-box ingredients whose contraction and robustness properties are taken as given.

pith-pipeline@v0.9.0 · 5589 in / 1306 out tokens · 47224 ms · 2026-05-16T12:36:40.171366+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Corollary 11 … |x⋆ℓ − xk+1ℓ|Aℓ ≤ q |x⋆ℓ − xkℓ|Aℓ … where q is the contraction factor from Lemma 10.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Adaptive finite element methods with optimally preconditioned GMRES guarantee optimal complexity
math.NA 2026-04 unverdicted novelty 6.0

An AFEM algorithm with optimally preconditioned GMRES achieves optimal complexity by using a feedback-controlled solver termination that enforces R-linear decay of a quasi-error measuring total error.