pith. sign in

arxiv: 2604.17947 · v1 · submitted 2026-04-20 · 🧮 math.NA · cs.NA

Adaptive finite element methods with optimally preconditioned GMRES guarantee optimal complexity

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

Pith reviewed 2026-05-10 04:24 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords adaptive finite element methodsGMRESoptimal complexityquasi-errormesh refinementpreconditioned iterative solverselliptic PDEs
0
0 comments X p. Extension

The pith

An adaptive algorithm controlling both mesh refinement and GMRES termination achieves unconditional convergence and optimal rates in total computational work for elliptic PDEs.

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

The paper develops a method for linear elliptic problems that refines the mesh locally while also deciding when to stop the GMRES iterations on the resulting discrete systems. It introduces a fully computable quasi-error that adds the discretization error to the remaining algebraic error from the iterative solver. A feedback rule adjusts the solver tolerance so that the combined quantity decreases at each step, which forces convergence no matter how the user sets the two adaptivity parameters. When those parameters are chosen small enough, the quasi-error decreases at the best possible rate measured against the total number of operations performed. This matters in practice because the cost of solving the linear systems often dominates the work of building finer meshes, and ignoring solver effort produces inefficient overall algorithms.

Core claim

We formulate an adaptive algorithm which steers the local mesh-refinement as well as the termination of a generalized minimal residual solver (GMRES) with optimal preconditioner to solve the arising non-symmetric finite element systems. Algorithmic interplay of mesh-refinement and iterative solver is shown to be optimal: A natural and fully computable quasi-error monitoring discretization error and algebraic solver error guarantees unconditional convergence for any choice of adaptivity parameters. This is ensured algorithmically via a novel adaptive feedback-control for the solver-termination parameter that monitors and ensures full R-linear convergence. Finally, the quasi-error even decays

What carries the argument

A fully computable quasi-error that sums the discretization error with the algebraic error from the GMRES solver, together with a feedback rule that adjusts the solver termination tolerance to guarantee linear decrease of this quantity.

If this is right

  • The combined algorithm converges for every choice of the two adaptivity parameters.
  • Optimal decay rates hold with respect to overall computational complexity once the parameters are chosen sufficiently small.
  • The quasi-error serves as a reliable monitor that drives both mesh refinement and solver termination.
  • The result applies to general second-order linear elliptic PDEs in the Lax-Milgram setting with non-symmetric discrete systems.

Where Pith is reading between the lines

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

  • The same style of feedback control on solver tolerance could be tested with other iterative solvers such as conjugate gradient on symmetric problems.
  • Implementation on concrete PDEs would show whether the predicted complexity gain appears in measured CPU time.
  • The theory requires the preconditioner to remain optimal uniformly across all refined meshes, which may need problem-specific construction.

Load-bearing premise

An optimal preconditioner exists for the non-symmetric finite-element systems on the adaptively refined meshes, and the AFEM marking strategy produces optimal rates once algebraic errors are controlled.

What would settle it

A computation on a standard elliptic test problem showing that the observed rate of the quasi-error versus total degrees of freedom times GMRES iterations falls below the optimal rate even after the adaptivity parameters are made very small.

Figures

Figures reproduced from arXiv: 2604.17947 by Ani Mira\c{c}i, Dirk Praetorius, Paula Hilbert, Thomas F\"uhrer.

Figure 1
Figure 1. Figure 1: Initial mesh (left), with #T0 = 48 elements, used to initialize Algorithm B together with polynomial degree p = 2 (leading to N0 = 81 initial degrees of freedom), bulk parameter θ = 0.5, and maximum PGMRES steps kmax = 5. The resulting mesh (center) after 10 refinements with #T10 = 3,396 elements (leading to N10 = 7,773 degrees of freedom) and corresponding approximation u k 10 (right). 101 102 103 104 105… view at source ↗
Figure 2
Figure 2. Figure 2: Rate-optimality of the Algorithm B using the additive Schwarz preconditioner from Section 3.2 for GMRES on the linear system with θ = 0.5 and kmax = 5 (left), kmax = 1 (right). First, we see in [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Cost-optimality of the Algorithm B using the additive Schwarz preconditioner from Section 3.2 for GMRES on the linear system, θ = 0.5 and kmax = 5 (left), kmax = 1 (right). 10−1 100 101 102 10−8 10−6 10−4 10−2 100 1/2 1 2 1 time error estimator ηℓ(u k ℓ ) p = 1 p = 2 p = 3 p = 4 10−2 10−1 100 101 102 10−8 10−6 10−4 10−2 100 1/2 1 2 1 time error estimator ηℓ(u k ℓ ) p = 1 p = 2 p = 3 p = 4 [PITH_FULL_IMAGE… view at source ↗
Figure 4
Figure 4. Figure 4: Optimal complexity of the Algorithm B using the additive Schwarz preconditioner from Section 3.2 for GMRES on the linear system, θ = 0.5 and kmax = 5 (left), kmax = 1 (right). (neither too large, nor too small) for a well-performing adaptive algorithm. In particular, the update of Calg and λalg seems to be independent of the choice of kmax. Next, let us discuss the stopping of the algebraic solver. While t… view at source ↗
Figure 5
Figure 5. Figure 5: Parameter adaptation in Algorithm B(ii.a) with respect to the degrees of freedom for θ = 0.5 and kmax = 5 (left), kmax = 1 (right). 101 102 103 104 105 106 0 5 10 number of degrees of freedom solver steps R k p = 1 p = 4 101 102 103 104 105 106 0 5 10 15 20 25 30 number of degrees of freedom solver steps R k p = 1 p = 4 [PITH_FULL_IMAGE:figures/full_fig_p021_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Iteration steps and number of restarts R = ⌊k[ℓ]/kmax⌋ for PGMRES with additive Schwarz preconditioner from Section 3.2 when em￾ploying Algorithm B for θ = 0.5 and kmax = 5 (left) and kmax = 1 (right). that, since Proposition 7 is ensured at each solver step, we indeed observe it numerically for different choices of kmax of PGMRES, in particular also for kmax = 1, i.e., we can restart at each step [PITH_F… view at source ↗
Figure 7
Figure 7. Figure 7: Contraction factors of the preconditioned residual for kmax = 5 (left) and kmax = 1 (right) for different polynomial degrees on a fixed mesh T20 (obtained by Algorithm B for p = 2) with #T20 = 99,085 elements. 0 50 100 150 200 250 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 iteration k contraction factor |||u ⋆ 20 −u k 20||| ∥||u ⋆ 20 −u k−1 20 ||| kmax = 1 kmax = 5 kmax = 300 0 50 100 150 200 250 10−14 10−11 10−8 1… view at source ↗
Figure 8
Figure 8. Figure 8: Contraction factors (left) and decrease (right) of the algebraic error in energy norm for p = 3 and different choices of kmax on a fixed mesh T20 (obtained by Algorithm B for p = 2) with #T20 = 99,085 elements. References [AFF+15] M. Aurada, M. Feischl, T. Führer, M. Karkulik, and D. Praetorius. Energy norm based error estimators for adaptive BEM for hypersingular integral equations. Appl. Numer. Math., 95… view at source ↗
read the original abstract

We analyze optimal complexity of adaptive finite element methods (AFEMs) for general second-order linear elliptic partial differential equations (PDEs) in the Lax-Milgram setting. To this end, we formulate an adaptive algorithm which steers the local mesh-refinement as well as the termination of a generalized minimal residual solver (GMRES) with optimal preconditioner to solve the arising non-symmetric finite element systems. Algorithmic interplay of mesh-refinement and iterative solver is shown to be optimal: A natural and fully computable quasi-error monitoring discretization error and algebraic solver error guarantees unconditional convergence for any choice of adaptivity parameters, i.e., the algorithm cannot fail to converge. This is ensured algorithmically via a novel adaptive feedback-control for the solver-termination parameter that monitors and ensures full R-linear convergence. Finally, the quasi-error even decays with optimal rates with respect to the overall computational complexity if the adaptivity parameters are chosen sufficiently small.

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 finite element method for general second-order linear elliptic PDEs in the Lax-Milgram setting. It couples local mesh refinement with termination of GMRES iterations (using an assumed optimal preconditioner) via a fully computable quasi-error that monitors both discretization and algebraic errors. A novel feedback-control mechanism on the solver tolerance is introduced to guarantee unconditional convergence for arbitrary adaptivity parameters; under sufficiently small parameters the quasi-error is shown to decay at optimal rates with respect to total computational complexity.

Significance. If the central claims hold, the work supplies a rigorous, parameter-robust theory for optimal-complexity AFEM that explicitly accounts for inexact algebraic solves in the non-symmetric case. The feedback-control device for solver termination is a concrete algorithmic contribution that prevents divergence even when parameters are chosen poorly, extending standard AFEM contraction arguments to the setting where algebraic error must be controlled.

major comments (2)
  1. [Abstract and §5] The optimality claim with respect to overall computational complexity (abstract and §5) rests on the existence of a mesh-independent optimal preconditioner whose setup and application costs remain linear in the number of degrees of freedom under local refinement. No explicit construction (e.g., multigrid, domain decomposition, or approximate Schur complement) or complexity analysis for this preconditioner on adaptively refined, non-symmetric systems is supplied; without it the total-complexity bound cannot be substantiated.
  2. [§4] §4 (quasi-error definition and contraction): the proof that the quasi-error contracts at a rate independent of the algebraic error relies on the marking strategy retaining its optimal rate once the algebraic error is a fixed fraction of the discretization error. The manuscript invokes this as a standard AFEM property but does not verify it for the non-symmetric Lax-Milgram setting under the specific feedback-control termination criterion.
minor comments (2)
  1. [§3] Notation for the quasi-error and the feedback-control parameter should be introduced with a dedicated definition block before the algorithm statement.
  2. [Introduction] The statement 'optimal preconditioner' is used repeatedly; a brief remark clarifying that the preconditioner is assumed to exist with bounded iteration count independent of mesh size would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. The comments highlight important aspects of the assumptions and proofs. We address each major comment below and indicate planned revisions to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Abstract and §5] The optimality claim with respect to overall computational complexity (abstract and §5) rests on the existence of a mesh-independent optimal preconditioner whose setup and application costs remain linear in the number of degrees of freedom under local refinement. No explicit construction (e.g., multigrid, domain decomposition, or approximate Schur complement) or complexity analysis for this preconditioner on adaptively refined, non-symmetric systems is supplied; without it the total-complexity bound cannot be substantiated.

    Authors: The manuscript assumes the existence of an optimal preconditioner for GMRES (mesh-independent convergence rate and linear complexity in setup/application) as part of the problem setting, consistent with the title and abstract phrasing 'optimally preconditioned GMRES'. The core contribution is the analysis of the AFEM-solver coupling via the quasi-error and feedback control, which guarantees convergence and optimal rates conditional on this assumption. We agree that an explicit construction or full complexity proof for non-symmetric adaptively refined systems is not provided and lies outside the paper's scope. We will revise the abstract and §5 to explicitly state the conditional nature of the total-complexity result and add a short discussion with citations to existing preconditioner constructions (e.g., algebraic multigrid or domain decomposition methods for non-symmetric elliptic problems) that achieve the required properties. revision: partial

  2. Referee: [§4] §4 (quasi-error definition and contraction): the proof that the quasi-error contracts at a rate independent of the algebraic error relies on the marking strategy retaining its optimal rate once the algebraic error is a fixed fraction of the discretization error. The manuscript invokes this as a standard AFEM property but does not verify it for the non-symmetric Lax-Milgram setting under the specific feedback-control termination criterion.

    Authors: The contraction argument in §4 proceeds by showing that the feedback control reduces the algebraic error to a fixed fraction of the current residual estimator, after which the standard AFEM contraction (estimator reduction plus bulk marking) applies to the quasi-error. The residual-based a posteriori estimator satisfies reliability and efficiency in the Lax-Milgram setting (coercive and continuous bilinear form) without requiring symmetry; see standard references for non-symmetric a posteriori analysis. The Dörfler marking property and resulting optimality of the marked set likewise hold under these assumptions, as the proof relies on the estimator's reduction property rather than symmetry. We will add a clarifying paragraph in §4 that explicitly verifies the applicability of the standard marking optimality result under the feedback-control criterion and non-symmetry. revision: yes

Circularity Check

0 steps flagged

No significant circularity; claims rest on external assumptions about preconditioners and AFEM rates

full rationale

The derivation establishes unconditional convergence and optimal complexity rates for the proposed AFEM-GMRES algorithm under the stated assumptions of an optimal preconditioner (mesh-independent GMRES iteration bounds) and standard AFEM contraction properties when algebraic error is controlled. These assumptions are invoked as given rather than derived internally or fitted to the target result. No self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citation chains appear in the abstract or described structure. The novel feedback-control mechanism for solver termination is algorithmic and does not reduce the quasi-error decay claim to a tautology. The result is therefore self-contained against external benchmarks for the given hypotheses.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The analysis relies on the Lax-Milgram theorem for well-posedness of the continuous problem and on standard a-posteriori error estimates for AFEM; no new entities are postulated.

free parameters (1)
  • adaptivity parameters (marking and solver tolerance)
    Must be chosen sufficiently small to obtain optimal rates, though any positive values suffice for convergence.
axioms (2)
  • standard math Lax-Milgram theorem guarantees unique solution in the given function space
    Invoked to place the PDE in the setting where AFEM theory applies.
  • domain assumption Existence of an optimal preconditioner for the discrete systems
    Required for the GMRES iteration to be efficient and for the algebraic error to be controllable.

pith-pipeline@v0.9.0 · 5468 in / 1372 out tokens · 45611 ms · 2026-05-10T04:24:27.415854+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages · 1 internal anchor

  1. [1]

    [Fei22] M

    doi: 10.1137/0720023. [Fei22] M. Feischl. Inf-sup stability implies quasi-orthogonality. Math. Comp., 91(337):2059– 2094, 2022. doi: 10.1090/mcom/3748. [FFP14] M. Feischl, T. Führer, and D. Praetorius. Adaptive FEM with optimal convergence rates for a certain class of nonsymmetric and possibly nonlinear problems.SIAM J. Numer. Anal., 52(2):601–625, 2014.d...

    work page doi:10.1137/0720023 2059

  2. [2]

    Generalized preconditioned conjugate gradients for adaptive FEM with optimal complexity

    doi: 10.1093/imanum/drx050. [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, 2021.doi: 10.1090/mcom/3654. [GMZ12] E. Garau, P. Morin, and C. Zuppa. Quasi-Optimal Convergence Rate of an AFEM for quasi-linear Problem...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1093/imanum/drx050 2011

  3. [3]

    [MN05] K

    doi: 10.1007/s00365-013-9192-4. [MN05] K. Mekchay and R. H. Nochetto. Convergence of adaptive finite element methods for general second order linear elliptic PDEs.SIAM J. Numer. Anal., 43(5):1803–1827,

    work page doi:10.1007/s00365-013-9192-4

  4. [4]

    [MNS00] P.Morin,R.Nochetto,andK.G.Siebert.Dataoscillationandconvergenceofadaptive FEM.SIAM J

    doi: 10.1137/04060929X. [MNS00] P.Morin,R.Nochetto,andK.G.Siebert.Dataoscillationandconvergenceofadaptive FEM.SIAM J. Numer. Anal.,38(2):466–488,2000. doi: 10.1137/s0036142999360044. [PP20] C. Pfeiler and D. Praetorius. Dörfler marking with minimal cardinality is a linear complexity problem. Math. Comp., 89(326):2735–2752, 2020.doi: 10.1090/mcom/ 3553. [P...

    work page doi:10.1137/04060929x 2000