A Unified Two-Grid Framework for Anderson Acceleration and Nonlinear GMRES
Abstract
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.
Related
- An Equivalence result for sketched Anderson Acceleration and sketched GMRES
- A nonmonotone globalization framework for Anderson acceleration for contractive and nonexpansive fixed point problems
- Acceleration of the Method of Alternating Projections on subspaces by GMRES
- A Projection Anderson Acceleration Algorithm for Non-quasi-monotone Variational Inequalities with Hölder Continuous Terms
- On a blended Anderson / NGMRES acceleration for the Navier-Stokes Picard iteration: convergence analysis and adaptive depth selection
BibTeX
@misc{adler2026unified,
title = {{A Unified Two-Grid Framework for Anderson Acceleration and Nonlinear GMRES}},
author = {James Adler and Yunhui He and Xiaozhe Hu and Satchel Lefebvre},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13091},
eprint = {2609.13091},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13091},
}
RIS
TY - UNPB
TI - A Unified Two-Grid Framework for Anderson Acceleration and Nonlinear GMRES
AU - James Adler
AU - Yunhui He
AU - Xiaozhe Hu
AU - Satchel Lefebvre
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.13091
UR - https://arxiv.org/abs/2609.13091
AB - 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.
ER -