pith. sign in

arxiv: 2605.20057 · v1 · pith:JTYUBOOZnew · submitted 2026-05-19 · 🧮 math.NA · cs.NA

Quasi-optimal complexity of iterative Galerkin methods driven by an elliptic reconstruction error estimator

Maximilian Brunner , Gregor Gantner , Christoph Lietz , Dirk Praetorius This is my paper

Pith reviewed 2026-05-20 03:51 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords quasilinear elliptic problemsGalerkin methodsZarantonello iterationadaptive mesh refinementa posteriori error estimationconvergence analysisquasi-optimal complexity
0
0 comments X

The pith

Elliptic reconstruction error estimator drives iterative Galerkin methods to unconditional R-linear convergence and quasi-optimal complexity.

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

The paper studies an adaptive algorithm for quasilinear elliptic problems that combines Galerkin discretization with damped Zarantonello linearization to solve the resulting nonlinear systems. It proves that a combined quasi-error measuring both linearization and discretization contributions converges R-linearly without any restrictions on the adaptivity parameters. When those parameters are chosen sufficiently small, the method attains optimal algebraic rates with respect to the number of degrees of freedom together with quasi-optimal complexity measured by total computational cost. A sympathetic reader cares because the results supply the first comprehensive convergence theory for this natural error estimator in the iterative nonlinear setting.

Core claim

We study an iterative Galerkin method for quasilinear elliptic problems in the Browder-Minty setting. The resulting discrete nonlinear systems are solved by linearization via a damped Zarantonello iteration. Unlike prior work, adaptive mesh refinement is driven by an elliptic reconstruction error estimator, which is natural in the sense that the a posteriori bounds for the linearization and discretization errors are well separated. For this setting, we present the first comprehensive convergence analysis of the corresponding algorithm. We prove unconditional full R-linear convergence of a suitable quasi-error that combines linearization and discretization errors. For sufficiently small adapt

What carries the argument

Elliptic reconstruction error estimator that separates a posteriori bounds for linearization and discretization errors to drive adaptive mesh refinement.

If this is right

  • The quasi-error combining linearization and discretization contributions decreases at a linear rate at every step of the algorithm.
  • Optimal algebraic convergence rates are attained with respect to the number of degrees of freedom once the adaptivity parameter is small enough.
  • Quasi-optimal complexity holds, so that the total computational work grows linearly with the achieved error reduction.
  • The separation property of the estimator permits independent control of linearization accuracy and mesh refinement.

Where Pith is reading between the lines

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

  • The same estimator-driven framework may extend directly to other monotone nonlinearities beyond the Browder-Minty class.
  • Balancing iteration count against mesh size via the separated estimator bounds could be automated in existing adaptive finite-element codes.
  • Similar quasi-error constructions might yield unconditional convergence proofs for related iterative schemes such as Newton or fixed-point methods.

Load-bearing premise

The a posteriori bounds for the linearization and discretization errors are well separated by the elliptic reconstruction error estimator.

What would settle it

Numerical runs in which the combined quasi-error fails to decrease linearly for any choice of adaptivity parameters, or in which observed rates with respect to degrees of freedom or total cost fall below the predicted optimal rates, would falsify the convergence and complexity claims.

Figures

Figures reproduced from arXiv: 2605.20057 by Christoph Lietz, Dirk Praetorius, Gregor Gantner, Maximilian Brunner.

Figure 1
Figure 1. Figure 1: Mesh-size functions hℓ , given by hℓ |T = |T| 1/2 for all T ∈ Tℓ , for the level ℓ = 15 mesh generated by Algorithm A for Benchmark 1. Refinement is steered either by the ζℓ(u k−1 ℓ ; z k ℓ ) from (16) (left) or by the standard estimator ηℓ(u k ℓ ) from (10) (right). The color bar applies to both plots. The parameters are set to u 0 0 = 0, θ = 0.5, Cmark = 1, λ = 0.1, δ = (1 − 2e −3/2 )/4, and p = 1. 101 1… view at source ↗
Figure 2
Figure 2. Figure 2: Convergence history (left) and number of linearization iterations (right) of Algorithm A over the number of degrees of freedom for Benchmark 1. The algorithm is steered by either the reconstruction estimator ζℓ(u k−1 ℓ ; z k ℓ ) from (16) (triangle) or by the standard estimator ηℓ(u k ℓ ) from (10) (circle). Solid markers correspond to the bulk parameter θ = 0.5 (adaptive mesh refinement), hol￾low markers … view at source ↗
Figure 3
Figure 3. Figure 3: Convergence history of the computable quasi-error Zek ℓ from (29) of Algorithm A for polynomial degrees p = 2 (square) and p = 4 (diamond) for Benchmark 1. Solid markers correspond to the bulk parameter θ = 0.5 (adaptive mesh refinement), hollow markers to θ = 1 (uniform mesh refinement). The parameters are set to u 0 0 = 0, Cmark = 1, λ = 0.1, and δ = (1 − 2e −3/2 )/4. Finally, although stability (A1) and… view at source ↗
Figure 4
Figure 4. Figure 4: Convergence history (left) of the error ∥∇( ⋆ u − u k ℓ )∥L2(Ω) and the number of linearization iterations (right) for the scalar products aH1 (· , ·) (circle), aµ(· , ·) (triangle), and a(ℓ,k) (· , ·) (square) for Benchmark 2. The parameters are set to u 0 0 = 0, θ = 0.5, Cmark = 1, λ = 0.1, δ = 1.5, and p = 1. convergence rates for aH1 (· , ·) with δ = 1.5 when a smaller value of λ is used. Overall, the … view at source ↗
read the original abstract

We study an iterative Galerkin method for quasilinear elliptic problems in the Browder-Minty setting. The resulting discrete nonlinear systems are solved by linearization via a (damped) Zarantonello iteration. Unlike prior work, adaptive mesh refinement is driven by an elliptic reconstruction error estimator, which is natural in the sense that the a posteriori bounds for the linearization and discretization errors are well separated. For this setting, we present the first comprehensive convergence analysis of the corresponding algorithm. We prove unconditional full R-linear convergence of a suitable quasi-error that combines linearization and discretization errors. For sufficiently small adaptivity parameters, we further establish optimal convergence rates with respect to the number of degrees of freedom and quasi-optimal complexity, i.e., optimal convergence rates with respect to the overall computational cost. Numerical experiments underpin 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.

Referee Report

2 major / 2 minor

Summary. The manuscript analyzes an adaptive iterative Galerkin method for quasilinear elliptic problems in the Browder-Minty setting. Discrete nonlinear systems are solved via damped Zarantonello iteration, with mesh refinement driven by an elliptic reconstruction error estimator that separates linearization and discretization errors. The central claims are unconditional R-linear convergence of a combined quasi-error and, for sufficiently small adaptivity parameters, optimal rates with respect to degrees of freedom together with quasi-optimal complexity with respect to total computational cost; numerical experiments are included to illustrate the theory.

Significance. If the derivations hold with uniform constants, the work would be a solid contribution to the numerical analysis of nonlinear PDEs. It supplies the first comprehensive convergence theory for this combination of iterative linearization and reconstruction-driven adaptivity, directly addressing the practical need for provably efficient solvers. The explicit separation of error sources via the elliptic reconstruction and the resulting unconditional linear convergence are technically useful strengths; the quasi-optimality result with respect to computational cost is a natural and desirable extension of existing adaptive FEM theory.

major comments (2)
  1. [§4] §4 (proof of R-linear convergence of the quasi-error): the reliability bound for the elliptic reconstruction estimator must be shown to absorb the coupling between the true nonlinearity and the linearized operator with a constant independent of both the local mesh size and the number of Zarantonello steps. If this constant grows with h or with the iteration index, the contraction factor for the combined quasi-error ceases to be uniform, undermining the unconditional convergence claim.
  2. [§5] §5 (quasi-optimality argument): the reduction to optimal rates for small adaptivity parameters relies on the estimator constants remaining bounded independently of the mesh sequence. The manuscript should explicitly track the dependence of these constants on the nonlinearity and on the damping parameter to confirm that the small-parameter regime is non-empty and mesh-independent.
minor comments (2)
  1. [§2] Notation for the quasi-error and the elliptic reconstruction should be introduced with a single consolidated definition rather than scattered across lemmas.
  2. [§6] The numerical experiments section would benefit from a table reporting the observed contraction factors and the measured effectivity indices of the estimator across successive iterations.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We are grateful to the referee for the thorough review and the positive overall assessment of our manuscript. We address the major comments in detail below and will incorporate clarifications and additional details in the revised version.

read point-by-point responses

  1. Referee: [§4] §4 (proof of R-linear convergence of the quasi-error): the reliability bound for the elliptic reconstruction estimator must be shown to absorb the coupling between the true nonlinearity and the linearized operator with a constant independent of both the local mesh size and the number of Zarantonello steps. If this constant grows with h or with the iteration index, the contraction factor for the combined quasi-error ceases to be uniform, undermining the unconditional convergence claim.

    Authors: We appreciate this important point. The reliability estimate for the elliptic reconstruction in the proof of the R-linear convergence relies on the uniform strong monotonicity and Lipschitz continuity of the nonlinearity in the Browder-Minty framework. These properties ensure that the constants in the estimator reliability are independent of the mesh size h and the Zarantonello iteration index, as the linearization is controlled by the fixed damping parameter. The contraction for the quasi-error then follows with a uniform factor less than one. To make this clearer, we will add an explicit remark in Section 4 clarifying the independence of these constants from h and the iteration count. revision: yes

  2. Referee: [§5] §5 (quasi-optimality argument): the reduction to optimal rates for small adaptivity parameters relies on the estimator constants remaining bounded independently of the mesh sequence. The manuscript should explicitly track the dependence of these constants on the nonlinearity and on the damping parameter to confirm that the small-parameter regime is non-empty and mesh-independent.

    Authors: Thank you for highlighting this. In the quasi-optimality argument of Section 5, the constants from the estimator reliability and efficiency depend on the strong monotonicity and Lipschitz constants of the operator and the damping parameter. These are fixed for the given problem and algorithm choice, hence independent of the mesh sequence. The smallness condition on the adaptivity parameter is chosen based on these fixed quantities, ensuring the regime is non-empty and mesh-independent. We will revise Section 5 to explicitly track this dependence. revision: yes

Circularity Check

0 steps flagged

No circularity; self-contained convergence analysis

full rationale

The paper derives unconditional R-linear convergence of a quasi-error and subsequent optimal rates from a posteriori bounds that separate linearization and discretization errors via elliptic reconstruction. These steps rely on standard Browder-Minty monotonicity arguments, reliability and efficiency of the estimator, and contraction mapping for the damped Zarantonello iteration, none of which reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations. The separation is asserted as natural for the setting and the constants are treated as uniform under the stated assumptions, yielding an independent proof rather than a tautology.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The analysis rests on the Browder-Minty monotonicity framework for the quasilinear operator and on the separation property of the chosen error estimator; these are domain-standard but constitute the main non-trivial inputs not derived inside the paper.

free parameters (1)
  • adaptivity parameters
    Must be chosen sufficiently small to obtain the optimal rates and quasi-optimal complexity; their specific values are not derived from first principles.
axioms (1)
  • domain assumption Quasilinear elliptic problems lie in the Browder-Minty setting
    Invoked to guarantee monotonicity and coercivity properties that enable the Zarantonello iteration and the error separation.

pith-pipeline@v0.9.0 · 5677 in / 1371 out tokens · 50606 ms · 2026-05-20T03:51:30.660506+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

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

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.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

  1. [1]

    Preprint

    arXiv:2512.19357. Preprint. [BDD04] P. Binev, W. Dahmen, and R. DeVore. Adaptive finite element methods with convergence rates.Numer. Math., 97(2):219–268,

    work page arXiv

  2. [2]

    Brunner, G

    [BGLP26] M. Brunner, G. Gantner, C. Lietz, and D. Praetorius. MooAFEM: Numerical investigation of an iterative Galerkin method driven by an elliptic reconstruction estimator for quasilinear elliptic PDEs, 2026.url: https://codeocean.com. Code Ocean capsule for the reproduction of the numerical results in this article, available under DOI: TBA. [BHP17] A. ...

    work page 2026

  3. [3]

    Preprint

    arXiv: 2601.20677. Preprint. [BPS25] M. Brunner, D. Praetorius, and J. Streitberger. Cost-optimal adaptive FEM with linearization and algebraic solver for semilinear elliptic PDEs. Numer. Math., 157(2):409–445,

    work page arXiv

  4. [4]

    Gantner, A

    [GHPS21] G. Gantner, A. Haberl, D. Praetorius, and S. Schimanko. Rate optimality of adaptive finite element methods with respect to overall computational costs.Math. Comp., 90(331):2011–2040,

    work page 2011

  5. [5]

    May 20, 2026 19 [Hei23] P. Heid. A short note on an adaptive damped Newton method for strongly monotone and Lipschitz continuous operator equations.Arch. Math. (Basel), 121(1):55–65,

    work page 2026

  6. [6]

    Mitra and M

    [MV23] K. Mitra and M. Vohralík. Guaranteed, locally efficient, and robust a posteriori estimates for nonlinear elliptic problems in iteration-dependent norms. An orthogonal decomposition result based on iterative linearization, 2023.url: https://inria. hal.science/hal-04156711. Preprint. [PP20] C.-M. Pfeiler and D. Praetorius. Dörfler marking with minima...

    work page 2023

  7. [7]

    (74) May 20, 2026 20 Then, F : Rd → Rd, F (ξ) := µ(|ξ|2)ξ satisfies eα |ξ − χ|2 ≤ F (ξ) − F (χ) · (ξ − χ) and |F (ξ) − F (χ)| ≤ eL |ξ − χ| for all ξ, χ ∈ Rd

    Let µ: [0, +∞) → [0, +∞) satisfy, for constants0 <eα ≤eL, the growth condition eα (t − s) ≤ µ(t2)t − µ(s2)s ≤eL (t − s) for all 0 ≤ s ≤ t. (74) May 20, 2026 20 Then, F : Rd → Rd, F (ξ) := µ(|ξ|2)ξ satisfies eα |ξ − χ|2 ≤ F (ξ) − F (χ) · (ξ − χ) and |F (ξ) − F (χ)| ≤ eL |ξ − χ| for all ξ, χ ∈ Rd. (75) Consequently, the induced PDE operatorA: H1 0(Ω) → H −1...

    work page 2026

  8. [8]

    Thus, F is Lipschitz continuous with constanteL

    Using the identity |σ − ρ|2 = 2 − 2σ · ρ (77) together with (76), it follows that |F (ξ) − F (χ)|2 = |g(s)σ − g(t)ρ|2 = g(s)2 − 2g(s)g(t)σ · ρ + g(t)2 (77) = |g(s) − g(t)|2 + g(s)g(t)|σ − ρ|2 (76) ≤ eL2 |s − t|2 + st|σ − ρ|2 (77) = eL2|sσ − tρ|2 =eL2|ξ − χ|2. Thus, F is Lipschitz continuous with constanteL. The estimates for A follow from (75) by integrat...

    work page 2026