pith. sign in

arxiv: 2505.08587 · v2 · pith:5PEFOFQWnew · submitted 2025-05-13 · 🧮 math.NA · cs.NA

Two-Level Sketching Alternating Anderson acceleration for Complex Physics Applications

Nicol\'as A. Barnafi , Massimiliano Lupo Pasini This is my paper

Pith reviewed 2026-05-22 15:45 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords Anderson accelerationsketchingfixed-point iterationpartial differential equationsnumerical accelerationphysics simulationsconvergence accelerationleast-squares reduction
0
0 comments X

The pith

A two-level sketching extension to Alternating Anderson acceleration reduces time-to-solution by up to 50 percent on PDE fixed-point problems without degrading convergence.

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

The paper develops a two-level sketching version of the Alternating Anderson-Picard method to accelerate fixed-point iterations that arise when discretizing single- and multi-physics PDEs. A static physics-based projection first reduces the least-squares subproblem to the most informative field, after which a dynamic algebraic sketching stage, guided by inexpensive stability estimators, further shrinks the system while preserving the original convergence behavior. The resulting algorithm alternates low-cost Picard steps with these reduced Anderson mixes, cuts memory traffic, and is shown to deliver substantial wall-clock savings on Stokes, p-Laplacian, Bidomain, and Navier-Stokes test cases at multiple problem sizes. A reader would care because many large-scale simulations spend the majority of their time inside such fixed-point loops; a reliable way to shrink that inner work directly shortens overall run times.

Core claim

The two-level sketching AAP algorithm solves reduced least-squares systems in place by combining a static, physics-informed projection with a dynamic sketching stage driven by backward stability analysis under Lipschitz continuity, yielding up to 50 percent reductions in time-to-solution relative to standard Anderson acceleration while leaving convergence rates unchanged on the listed benchmark families.

What carries the argument

Two-level sketching: a static physics-based projection (via Schur-complement insight) that selects the most informative field, paired with a dynamic algebraic sketching stage that uses inexpensive stability-threshold estimators and cache-aware randomized selection to shrink the least-squares problem.

If this is right

  • The reduced least-squares solves can be performed in place, lowering both memory footprint and cache misses during each Anderson step.
  • The method alternates Picard updates and sketched Anderson mixes without requiring changes to the outer nonlinear solver loop.
  • The same static-plus-dynamic structure applies across different physics discretizations, as demonstrated on Stokes, p-Laplacian, Bidomain, and Navier-Stokes formulations.
  • Open-source Julia implementation allows direct reuse inside existing high-performance PDE codes.

Where Pith is reading between the lines

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

  • The stability estimators could be reused to adapt the sketching dimension on the fly inside a single run rather than fixing it in advance.
  • Because the static projection exploits problem-specific structure, the same two-level idea may transfer to other acceleration families that also rely on least-squares corrections.
  • Extending the dynamic stage to exploit GPU-friendly batched linear algebra would be a natural next measurement on the same benchmark suite.

Load-bearing premise

The dynamic sketching decisions rest on the assumption that the underlying fixed-point map is Lipschitz continuous so that the backward stability analysis can supply reliable thresholds.

What would settle it

A single benchmark run on Stokes or Navier-Stokes in which the sketched version either increases total wall-clock time or visibly slows the convergence rate compared with plain Anderson acceleration would refute the claim of consistent improvement without degradation.

read the original abstract

We present a novel two-level sketching extension of the Alternating Anderson-Picard (AAP) method for accelerating fixed-point iterations in challenging single- and multi-physics simulations governed by discretized partial differential equations. Our approach combines a static, physics-based projection that reduces the least-squares problem to the most informative field (e.g., via Schur-complement insight) with a dynamic, algebraic sketching stage driven by a backward stability analysis under Lipschitz continuity. We introduce inexpensive estimators for stability thresholds and cache-aware randomized selection strategies to balance computational cost against memory-access overhead. The resulting algorithm solves reduced least-squares systems in place, minimizes memory footprints, and seamlessly alternates between low-cost Picard updates and Anderson mixing. Implemented in Julia, our two-level sketching AAP achieves up to 50% time-to-solution reductions compared to standard Anderson acceleration-without degrading convergence rates-on benchmark problems including Stokes, p-Laplacian, Bidomain, and Navier-Stokes formulations at varying problem sizes. These results demonstrate the method's robustness, scalability, and potential for integration into high-performance scientific computing frameworks. Our implementation is available open-source in the AAP.jl library.

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 introduces a two-level sketching extension to the Alternating Anderson-Picard (AAP) method for accelerating fixed-point iterations arising from discretized PDEs in single- and multi-physics settings. It combines a static physics-based projection (reducing the least-squares problem via Schur-complement insight) with a dynamic algebraic sketching stage justified by backward stability analysis under an assumed Lipschitz continuity of the fixed-point map, together with inexpensive threshold estimators and cache-aware randomized selection. The central empirical claim is that the resulting algorithm delivers up to 50% time-to-solution reductions relative to standard Anderson acceleration on Stokes, p-Laplacian, Bidomain, and Navier-Stokes benchmarks at varying sizes, without degrading convergence rates, and is implemented in the open-source AAP.jl library.

Significance. If the performance gains and convergence preservation hold, the method could provide a practical, memory-efficient acceleration technique for large-scale scientific computing workflows that already employ Anderson mixing. The open-source release and focus on cache-aware implementation are positive contributions that facilitate reproducibility and adoption in high-performance PDE solvers.

major comments (2)
  1. [§3.2] §3.2 (Backward stability analysis): The dynamic sketching stage is derived under the assumption that the fixed-point map is Lipschitz continuous with a bounded constant that the inexpensive estimators can reliably detect. For the p-Laplacian (p>2) and convective Navier-Stokes cases the map is at best locally Lipschitz; the manuscript does not provide a concrete test or fallback mechanism showing that the reduced least-squares solve remains stable when the estimator under-predicts the threshold, which directly bears on the claim that convergence rates are preserved.
  2. [Results section] Results section / Table 2 (or equivalent benchmark table): The headline 50% time-to-solution reduction is stated without reported standard deviations, number of independent runs, precise baseline implementation details (e.g., whether the reference Anderson solver uses the same inner linear solver tolerances), or explicit measurement of asymptotic convergence rates versus iteration counts. These omissions make it impossible to assess whether the observed speedups are statistically robust or whether any hidden increase in iteration count is masked by wall-clock savings.
minor comments (2)
  1. [Abstract] The abstract and §1 use the phrase “without degrading convergence rates” without clarifying whether this refers to the asymptotic linear rate, the number of outer iterations to a fixed tolerance, or both; a short clarifying sentence would remove ambiguity.
  2. [§2] Notation for the stability threshold estimators (e.g., symbols for the Lipschitz constant estimator and the sketching dimension) is introduced without a consolidated table of symbols, which would aid readers working through the algorithmic description.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment point by point below, providing clarifications based on the existing analysis and benchmarks while indicating revisions that will strengthen the presentation.

read point-by-point responses

  1. Referee: [§3.2] §3.2 (Backward stability analysis): The dynamic sketching stage is derived under the assumption that the fixed-point map is Lipschitz continuous with a bounded constant that the inexpensive estimators can reliably detect. For the p-Laplacian (p>2) and convective Navier-Stokes cases the map is at best locally Lipschitz; the manuscript does not provide a concrete test or fallback mechanism showing that the reduced least-squares solve remains stable when the estimator under-predicts the threshold, which directly bears on the claim that convergence rates are preserved.

    Authors: The backward stability analysis in §3.2 relies on the Lipschitz continuity assumption for the fixed-point map, which is standard for Anderson-type methods and holds globally for linear and mildly nonlinear problems. For the p-Laplacian (p>2) and convective Navier-Stokes, the map is locally Lipschitz, as noted in the literature on these discretizations. The inexpensive threshold estimators are designed to detect deviations, and the reported benchmarks on these exact problems demonstrate that convergence rates are preserved without instability in the reduced solves. To address the request for a concrete test, we will expand §3.2 with a discussion of the local Lipschitz regime, add numerical verification from the existing p-Laplacian and Navier-Stokes runs showing estimator reliability, and describe a simple fallback (revert to full Anderson when the estimated constant exceeds a safety threshold). These additions will be included in the revised manuscript. revision: yes

  2. Referee: Results section / Table 2 (or equivalent benchmark table): The headline 50% time-to-solution reduction is stated without reported standard deviations, number of independent runs, precise baseline implementation details (e.g., whether the reference Anderson solver uses the same inner linear solver tolerances), or explicit measurement of asymptotic convergence rates versus iteration counts. These omissions make it impossible to assess whether the observed speedups are statistically robust or whether any hidden increase in iteration count is masked by wall-clock savings.

    Authors: We agree that additional statistical and implementation details would improve the clarity and robustness assessment of the results. The current manuscript reports wall-clock reductions on the listed benchmarks while stating that convergence rates are preserved, with the baseline being a standard Anderson implementation under identical solver settings. In the revised version, we will update the Results section and benchmark table to report standard deviations over a specified number of independent runs, explicitly confirm matching inner linear solver tolerances and hardware for the baseline, and include iteration counts together with asymptotic rate measurements (or references to convergence plots) to confirm no hidden iteration increase. These changes will be made without altering the reported performance claims. revision: yes

Circularity Check

0 steps flagged

No load-bearing circularity; central claims rest on independent benchmarks and analysis

full rationale

The paper constructs a two-level sketching AAP extension by combining a static physics-based projection (reducing the least-squares problem via Schur-complement insight) with a dynamic sketching stage justified by a backward stability analysis that assumes Lipschitz continuity of the fixed-point map and introduces inexpensive estimators for stability thresholds. These elements are presented as a novel algorithmic contribution implemented in AAP.jl, with performance claims (up to 50% time-to-solution reductions without degrading rates) validated through numerical experiments on external benchmark problems including Stokes, p-Laplacian, Bidomain, and Navier-Stokes at varying sizes. No derivation step reduces by the paper's own equations to a fitted parameter renamed as prediction, a self-definitional loop, or a load-bearing self-citation chain; the stability analysis and benchmarks supply independent content. This is the most common honest outcome for a self-contained algorithmic paper with external validation.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The method rests on standard numerical-analysis assumptions plus a small number of introduced estimators; no new physical entities are postulated.

free parameters (1)
  • stability thresholds
    Inexpensive estimators for stability thresholds are introduced to control the dynamic sketching stage.
axioms (1)
  • domain assumption Lipschitz continuity of the fixed-point iteration map
    Invoked to justify the backward stability analysis that drives the dynamic sketching.

pith-pipeline@v0.9.0 · 5731 in / 1297 out tokens · 41574 ms · 2026-05-22T15:45:02.516431+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.

Forward citations

Cited by 1 Pith paper

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

  1. A modified Anderson acceleration with sharp linear convergence rate predictions and application to incompressible flows

    math.NA 2026-05 unverdicted novelty 6.0

    The paper introduces AAg, a nonlinear-residual variant of Anderson acceleration, proves sharp linear convergence rates for arbitrary depth on Picard iterations for Navier-Stokes, and proposes an adaptive depth strateg...