PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Two-Grid Framework for Anderson Acceleration and Nonlinear GMRES

James Adler, Yunhui He, Xiaozhe Hu, Satchel Lefebvre

arXiv:2609.13091v1math.NAcs.NA

TL;DR

The paper asks how AA and NGMRES, along with their existing variants, can be understood within a common framework beyond their separate least-squares formulations. The paper derives error propagation matrices for AA and NGMRES on linear problems and reformulates them as two-grid methods with a projection-based coarse-grid correction. The new variant often outperforms AA, NGMRES, and their variants on the SPD Poisson and non-SPD convection-diffusion problems, with its advantage growing as convection dominance increases.

  • Problem

    The paper asks how AA and NGMRES, along with their existing variants, can be understood within a common framework beyond their separate least-squares formulations.

    Source: §2.3 · p. 5, §4 · p. 9

  • Method

    The paper derives error propagation matrices for AA and NGMRES on linear problems and reformulates them as two-grid methods with a projection-based coarse-grid correction.

    Source: §2.3 · p. 5, §6 · p. 15

  • Results

    The new variant often outperforms AA, NGMRES, and their variants on the SPD Poisson and non-SPD convection-diffusion problems, with its advantage growing as convection dominance increases.

    Source: §6 · p. 16

  • Takeaways & Limitations

    The two-grid formulation recovers existing methods as special cases and provides a flexible framework for designing variants by changing smoothing steps or the coarse space.

    Source: §4 · p. 9, §6 · p. 15

    Changing the ℓ2 norm is not considered in this paper.

    Source: §2.2 · p. 4

Abstract

from arXiv · show

In this work, we recast two widely used acceleration methods for fixed-point iterations, Anderson acceleration (AA) and the nonlinear generalized minimal residual method (NGMRES), as two-grid methods. By explicitly deriving the error propagation matrices for AA and NGMRES on linear problems, we show that both methods, together with several of their existing variants, can be reformulated as two-grid methods with a single pre- or postsmoothing step and a coarse-grid correction given by a projection with respect to a suitable inner product. This reformulation not only unifies AA, NGMRES, and their variants within a single algorithmic framework, but also enables the design of new variants by independently adjusting the components of the two-grid method, such as the coarse space and the smoothing steps. In particular, we propose a new variant that enlarges the coarse space by incorporating the most recently updated residual, an improvement that is naturally revealed by the two-grid formulation but is hidden in the standard formulations of the AA and NGMRES algorithms. Numerical experiments on both an SPD Poisson problem and a family of non-SPD convection-diffusion problems show that this new variant often outperforms both AA and NGMRES, as well as their variants.

1. Introduction.

The paper places Anderson acceleration (AA) and NGMRES in a unified two-grid framework, building on earlier work connecting them to GMRES and studying their variants. It reports that its new variant often outperforms AA, NGMRES, and their variants on the tested problems.

1. Introduction.

  • Earlier work connected AA and NGMRES to GMRES, including equivalences under specified conditions.AA is equivalent to GMRES under certain conditions, while NGMRES applied to Richardson’s iteration for linear systems is also equivalent to GMRES.Source: §1 · p. 1
  • Prior variants have explored different norms and least-squares formulations for AA and NGMRES.The classical methods use the ℓ2 norm; other variants change the norm or the least-squares problem.Source: §1 · pp. 1–2
  • The unified two-grid framework recovers existing AA and NGMRES variants and enables a new variant that often outperforms them on Poisson and convection-diffusion problems.The new variant’s advantage grows as the convection-diffusion problem becomes more convection-dominated.Source: §1 · p. 2

2. Preliminaries.

The preliminaries establish the fixed-point iteration and its residuals, introduce NGMRES and AA variants, and recall the standard two-grid method used as the basis for their reformulation.

2. Preliminaries.

  • The linear system uses a fixed-point iteration with B as a preconditioner; its fixed-point residual is f(xk) = Brk, and m denotes the fixed history window.When m is not fixed and equals k at every step, the methods are called full AA and full NGMRES.Source: §2 · pp. 2–3

2.1. Nonlinear GMRES.

  • NGMRES forms the next iterate from a fixed-point update and previous iterates, choosing coefficients through a minimization problem; NGMRESf changes the least-squares problem.The remaining NGMRESf steps are the same as in NGMRES.Source: §2.1 · p. 3

2.2. Anderson Acceleration.

  • AA combines the current fixed-point update with previous updates and uses a different least-squares problem to choose its coefficients.AAr and AAf are additional AA variants that use different least-squares problems.Source: §2.2 · pp. 3–4
  • The methods classically use the ℓ2 norm, while the two-grid approach can extend to other norms with adjusted derivations.The paper does not consider those norm changes here.Source: §2.2 · p. 4

2.3. Two-grid Methods.

  • The standard two-grid method uses fixed-point iteration for smoothing and a coarse-grid correction; the paper recasts AA and NGMRES by matching their linear error propagators to the two-grid error equation.The coarse-grid correction is a projection onto Range(P), with its inner product determining the restriction choice.Source: §2.3 · pp. 4–5

3. AA and NGMRES as Two-Grid Methods.

The paper derives linear-problem error equations that recast NGMRES and its variant, then AA and its variants, as two-grid methods. These formulations use a coarse-grid projection and a single presmoothing or postsmoothing step, respectively.

3.1. NGMRES and NGMRESf.

  • The NGMRES error derivation represents its coarse-grid correction as a projection onto an iteration-dependent coarse space.The NGMRESf formulation is also recovered as a two-grid method by selecting its corresponding prolongation and projection inner product.Source: §3.1 · pp. 5–6
  • NGMRES and NGMRESf are two-grid methods with one presmoothing step and iteration-dependent coarse spaces defined through projections.For NGMRES, choosing the stated prolongation and restriction recovers the original method.Source: §3.1 · p. 6

3.2. Anderson Acceleration and Variants.

  • Error equations for AA, AAr, and AAf connect each method to a two-grid scheme with a coarse-grid correction followed by postsmoothing.The variants differ in their projections onto the coarse space, including the inner product used.Source: §3.1 · p. 7, §3.2 · p. 8

3. AA and NGMRES as Two-Grid Methods.

  • AA, AAr, AAf, and NGMRES variants can all be expressed using a smoothing step and a coarse-grid correction.The two-grid formulation summarizes the variants through their different coarse spaces and projections.Source: §3.2 · pp. 8–9

4. A General Two-Grid Acceleration Method.

The unified two-grid framework recovers AA, NGMRES, and their variants while allowing independent choices of coarse space, projection, and smoothing. Its specific variant adds the most recently updated residual to the coarse space.

4. A General Two-Grid Acceleration Method.

  • The framework recovers AA, NGMRES, and existing variants while allowing changes to the coarse space, projection, and number or placement of smoothing steps.Different projection inner products yield corresponding restrictions, avoiding a separately formulated least-squares problem for each variant.Source: §4 · pp. 9–10
  • The prolongation matrix matters because the coarse space should capture low-frequency or otherwise difficult-to-converge error components.The added residual is motivated as potentially capturing more information about those error components.Source: §4.1 · p. 10

4.1. A Specific Variant.

  • The specific variant adds the most recently updated residual to the coarse space when presmoothing is used.Because the residual is updated during presmoothing, the added term is B r_{k+1}, rather than B r_k; the formulation also drops the oldest iterate to keep the coarse-space dimension unchanged.Source: §4.1 · pp. 10–11
  • The framework also allows adjustment of smoothing steps, but the experiments mainly use one presmoothing step and no postsmoothing for comparison with NGMRES.The stated setting is ν1 = 1 and ν2 = 0.Source: §4.1 · p. 11

5. Numerical Results.

The experiments verify the two-grid reformulations and compare the new TGA variant with AA, NGMRES, and their variants on Poisson and convection-diffusion problems. TGA performs best in most tested settings, while larger windows are not uniformly beneficial for convection-dominated problems.

5. Numerical Results.

  • The Poisson tests use 256 × 256 and 1024 × 1024 matrices; convection-diffusion tests use the same sizes and η values 1, 10^-3, and 10^-6.The Poisson stopping criterion is a relative residual reduction of 10^-10; the convection-diffusion tests use the same tolerance.Source: §5.1 · p. 11, Table 5.1 · p. 12, §5.2 · p. 13

5.1. SPD Example: Poisson’s Equation.

  • On Poisson, NGMRES(1) converges faster than AA(1), and the two-grid formulations match their corresponding standard methods.The authors attribute NGMRES(1)'s faster convergence to its equivalence to GMRES for SPD A.Source: §5.1 · p. 12, Figure 5.1 · p. 12
  • For Poisson, NGMRES and NGMRESf iteration counts stay constant across window sizes, while AA and its variants improve with larger m but remain slower.AAr and AAf have equal iteration counts in this setting; the authors attribute variant equivalences to B being a scaled identity.Source: §5.1 · pp. 12–13

5.2. Non-SPD Example: the Convection-Diffusion Equation.

  • TGA(m; 1, 0) outperforms the compared methods for m ≥2 on Poisson and the diffusion-dominated case, and is best across tested m in convection-dominated cases.For η = 10^-3 and η = 10^-6, it is best at every tested window size.Source: §5.1 · p. 13, §5.2 · pp. 14–15
  • At η = 1, NGMRES and NGMRESf are generally more effective than AA and its variants, while TGA outperforms the other methods for m ≥2.η = 1 is the diffusion-dominated case.Source: §5.2 · p. 14, Table 5.2 · p. 14
  • In the tested convection-dominated cases, iteration counts grow with m for all methods, so larger windows do not uniformly improve performance.This trend is reported for η = 10^-3 and η = 10^-6.Source: Table 5.3 · p. 14, §5.2 · p. 15, Table 5.4 · p. 15

6. Conclusion.

The paper unifies AA, NGMRES, and several variants as two-grid methods, then uses this formulation to propose a flexible accelerator. Its new variant often outperforms the existing methods in the tested Poisson and convection-diffusion problems.

6. Conclusion.

  • The two-grid framework reformulates AA, NGMRES, AAr, AAf, and NGMRESf using one smoothing step and a projected coarse-grid correction.The methods' differences are expressed through coarse-space and inner-product choices.Source: §6 · p. 16
  • The new variant adds the most recently updated residual to the coarse space and often outperforms AA, NGMRES, and their variants in the tested problems.Its advantage grows as the convection-diffusion problem becomes increasingly convection-dominated.Source: §6 · p. 16
  • Multilevel and nonlinear extensions of the framework are identified as future work and are ongoing.The authors also anticipate that flexible smoothing and coarse-space choices may support further variants tailored to problem classes.Source: §6 · p. 16
Loading 2609.13091v1…