🔢 mathematics

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

This paper extends a modified Anderson acceleration method (AAg) that utilizes nonlinear residuals to accelerate Picard iterations for incompressible Navier-Stokes equations, providing a sharp linear convergence rate prediction and an adaptive depth selection strategy validated by numerical experiments.

Original authors: Yunhui He, Leo Rebholz

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yunhui He, Leo Rebholz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding a Needle in a Haystack

Imagine you are trying to find a specific spot on a map (the solution to a complex physics problem involving fluid flow, like water moving through a pipe or around a block). You have a rough method to guess where you are, but it's slow. It's like taking one tiny step forward, checking your map, taking another tiny step, checking again, and repeating this thousands of times. This is called Picard iteration.

Sometimes, this method is so slow it feels like you aren't moving at all, or worse, it wanders off in the wrong direction.

The Solution: "Anderson Acceleration" (The Smart Navigator)

To fix this, mathematicians use a trick called Anderson Acceleration (AA). Think of this as a smart navigator. Instead of just taking one step, the navigator looks at your last few steps (your history). It asks: "Based on where I've been, what is the best single jump I can make to get closer to the target?" It solves a small math puzzle to figure out the perfect mix of your past moves to create a giant, efficient leap forward.

The New Innovation: "AAg" (The Better Compass)

The authors of this paper introduced a new, improved version of this navigator called AAg.

In the old versions (standard AA and another method called NGMRES), the navigator looked at the "distance to the goal" using a standard ruler (the fixed-point residual). However, the authors realized that for fluid problems (like water flow), there is a better, more accurate ruler (the nonlinear residual).

The Analogy: Imagine you are trying to hit a bullseye.
- Old Method (AA): You measure your distance from the center using a tape measure that is slightly stretched. You get a good idea, but it's not perfect.
- New Method (AAg): You use a laser measure that is perfectly calibrated for the specific terrain you are walking on. It tells you exactly how far you are from the target in a way that makes sense for the physics of the problem.

The Two Major Breakthroughs

1. Predicting the Speed (The Crystal Ball)

One of the biggest headaches with these acceleration methods is knowing how deep to look into your history.

Depth ( $m$ ): This is how many past steps the navigator looks back at.
- If you look back too little (Depth = 1), you don't get enough help.
- If you look back too much (Depth = 100), you might get confused by old, irrelevant data and make a mistake.
The Problem: Usually, you have to guess the right depth. It's like trying to guess how many ingredients to put in a soup without tasting it.
The AAg Breakthrough: Because AAg uses that "perfect laser measure," the authors proved mathematically that they can predict exactly how fast the method will converge at every single step. They can calculate a "speedometer" reading before they even take the next step. This is something previous methods couldn't do with such precision.

2. The Self-Adjusting Strategy (The Smart Thermostat)

Because they can predict the speed so accurately, they created an adaptive strategy.

How it works: The method starts by looking back at only a few steps (small depth). As it gets closer to the solution and the "speedometer" shows it's safe, it automatically starts looking back at more steps (increasing the depth).
The Analogy: Think of driving a car. When you are far from your destination on a straight highway, you can cruise at high speed (large depth). But when you are entering a tricky, winding neighborhood (where the math gets messy), you slow down and look at the immediate road ahead (small depth).
The Result: The paper shows that this "self-adjusting" AAg is much faster than using a fixed setting. It saves a massive amount of time and computer power, especially for difficult 3D problems like blood flow in a narrowed artery or air moving around a block.

What They Tested

The authors tested this on three real-world scenarios:

Water flowing past a block: A classic 2D test.
Air swirling in a 3D box: A 3D test.
Blood flowing through a narrowed artery: A complex 3D medical model.

In almost every case, the new AAg method was slightly better or equal to the old methods, but the adaptive AAg (the one that changes its own settings) was a clear winner, solving difficult problems that the other methods struggled with or failed to solve entirely.

Summary

This paper presents a smarter way to solve complex fluid flow equations. By using a more accurate "ruler" to measure progress, the new AAg method can predict its own speed. This prediction allows it to automatically adjust how much history it uses, making it faster and more reliable than previous methods, particularly for difficult 3D simulations.

Technical Summary: A Modified Anderson Acceleration with Sharp Linear Convergence Rate Predictions and Application to Incompressible Flows

Problem Statement
The paper addresses the challenge of accelerating fixed-point iterations for solving nonlinear partial differential equations, specifically the steady-state Navier-Stokes equations (NSE). While Anderson Acceleration (AA) is a widely used method for improving fixed-point convergence, existing theoretical frameworks often lack sharp predictions of linear convergence rates. Furthermore, there is limited theoretical guidance on how to optimally select the depth parameter ( $m$ ) for AA, which is crucial for balancing convergence speed against the influence of higher-order error terms. The authors also note that the nonlinear GMRES (NGMRES) method, which utilizes the nonlinear residual rather than the fixed-point residual, offers sharper convergence predictions in certain settings, prompting an investigation into whether AA can be similarly modified.

Methodology
The authors propose and analyze a modified variant of Anderson Acceleration, termed AAg (Anderson acceleration with $g$ -norm). Unlike standard AA, which minimizes the fixed-point iteration residual, AAg minimizes the nonlinear residual operator $g(\cdot)$ within the least-squares problem used to determine combination coefficients.

The methodology involves three main components:

Algorithmic Formulation: The paper defines AAg (Algorithm 3) where the update step $u_{k+1}$ is a linear combination of previous Picard iterates $q(u_j)$ , determined by solving a least-squares problem that minimizes the norm of the nonlinear residual $g(u)$ . The optimization is performed in the dual space norm $\|\cdot\|_{V'}$ , which is appropriate for the NSE nonlinear residual.
Convergence Analysis: The authors establish a convergence theory for AAg with arbitrary depth $m$ . They derive error bounds showing that the convergence rate is governed by the gain of the optimization problem. Crucially, they define a quantity $\gamma_{k+1}$ , which represents the ratio of the predicted residual to the current residual. The analysis demonstrates that $\gamma_{k+1}$ provides a sharp prediction of the linear convergence rate once higher-order terms become negligible.
Adaptive Strategy: Motivated by the sharpness of the $\gamma_k$ prediction, the authors develop an adaptive strategy for selecting the depth parameter $m$ . The strategy starts with a small depth and increases $m$ only when the difference between the predicted rate $\gamma_k$ and the observed rate becomes negligible (indicating that higher-order terms are no longer dominant). This aims to avoid the instability associated with large $m$ when the iterate is far from the solution.

Key Contributions

Extension of AAg: The work extends the AAg method, previously studied only for linear problems, to the nonlinear Picard iteration for the NSE.
Sharp Convergence Prediction: The primary theoretical contribution is the derivation of a convergence analysis that yields a sharp prediction of the linear convergence rate ( $\gamma_k$ ) for general depth $m$ . This is a feature not present in the known theory for classical AA.
Adaptive Depth Selection: The paper introduces a practical adaptive strategy for choosing the depth $m$ based on the sharp convergence prediction $\gamma_k$ , addressing the open question of how to best select this parameter.
Comprehensive Numerical Comparison: The study provides extensive numerical comparisons between AAg, standard AA, and NGMRES across various 2D and 3D flow benchmarks (channel flow past a block, driven cavity, and stenotic artery).

Numerical Results
The authors conducted numerical experiments on 2D and 3D NSE problems with varying Reynolds numbers ($Re$).

Performance: AAg and standard AA performed similarly and generally slightly better than NGMRES for the tested problems. In difficult cases (e.g., $Re=150$ 2D channel flow), both AA and AAg converged where NGMRES failed or converged very slowly.
Prediction Accuracy: The numerical results confirmed that $\gamma_k$ is a highly accurate predictor of the linear convergence rate once the residual is sufficiently reduced, validating the theoretical analysis.
Adaptive Strategy Effectiveness: The adaptive depth strategy significantly improved performance. For challenging problems where constant large depths failed (e.g., $Re=200$), the adaptive approach successfully converged by starting with small depths and increasing them as the solution approached the root.
Computational Cost: The authors note that using the $V'$ norm for optimization requires an additional Stokes solve per iteration, increasing computational time by approximately 20% compared to methods using the $\ell_2$ norm. However, this cost is deemed necessary for the theoretical consistency and improved 3D performance.

Significance and Claims
The paper claims that the AAg method offers a distinct theoretical advantage over classical AA by providing a sharp, step-by-step prediction of the linear convergence rate. This capability is not merely theoretical but serves as the foundation for a robust adaptive strategy that automatically selects the optimal depth parameter. The authors assert that while AAg and AA exhibit similar performance with fixed depths, the ability to predict convergence rates allows AAg to adaptively manage the trade-off between linear acceleration and higher-order error terms more effectively. The work suggests that this approach is particularly valuable for complex nonlinear problems like the NSE, where fixed parameter choices are often suboptimal. The authors conclude that these results lay the groundwork for extending AAg theory to broader applications and developing more sophisticated adaptive strategies.