🔢 mathematics

Convergence analysis and proof of acceleration for NGMRES applied to the Picard iteration for Navier-Stokes equations

This paper presents the first convergence analysis and proof of acceleration for nonlinear GMRES (NGMRES) applied to the Picard iteration for Navier-Stokes equations, identifying the optimal norm and demonstrating that NGMRES scales the Lipschitz constant to significantly improve convergence, even in divergent cases.

Original authors: Yunhui He, Leo G Rebholz

Published 2026-04-15

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Yunhui He, Leo G 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

Imagine you are trying to navigate a massive, foggy maze to find the exit. This maze represents the Navier-Stokes equations, which are the complex mathematical rules that describe how fluids (like water, air, or blood) move. Solving these equations is crucial for designing airplanes, predicting weather, and understanding blood flow, but it's notoriously difficult.

To find the solution, mathematicians use a method called Picard iteration. Think of this as taking a step, looking at where you are, taking another step based on that new position, and repeating. It's a "guess and check" process.

However, there's a problem: sometimes the maze is so twisty (high "Reynolds number," which means the fluid is moving fast and turbulently) that this simple step-by-step method gets stuck, wanders in circles, or even runs away from the exit entirely.

The New Tool: NGMRES

This paper introduces a smarter way to navigate the maze called NGMRES (Nonlinear GMRES).

Instead of just looking at your current step, NGMRES looks at your last few steps. It asks: "Based on where I've been in the last 5 or 10 moves, what is the best single direction to jump to get closer to the exit?"

It's like having a GPS that doesn't just tell you to "turn left," but analyzes your entire recent path to calculate a shortcut that skips the confusing loops.

The Big Discovery: The "Right Ruler"

The most important finding in this paper is about how to measure success.

When the algorithm tries to find that best shortcut, it has to solve a mini-math problem (an optimization problem). To solve this, it needs to measure "distance."

The Old Way: Most people use a standard ruler (called the $\ell_2$ norm). It's like measuring distance with a standard tape measure. It works fine for simple, flat mazes (2D problems).
The New Way: The authors discovered that for complex, 3D fluid problems, the standard ruler is the wrong tool. It's like trying to measure the volume of a cloud with a tape measure. You need a specialized, flexible ruler (called the $V'$ norm) that understands the specific shape of the fluid's movement.

The Analogy:
Imagine trying to pack a suitcase.

If you use a standard ruler ( $\ell_2$ ) to decide how to fold your clothes, you might end up with a messy, inefficient pack, especially if the clothes are weird shapes (3D turbulence).
If you use a specialized folding guide ( $V'$ norm) designed specifically for those clothes, you fit everything in perfectly and efficiently.

The paper proves mathematically that using this "specialized ruler" is the secret sauce that makes the algorithm work. In 3D simulations, using the old ruler actually makes the algorithm fail, while the new ruler makes it fly.

What the Math Proves

The authors didn't just guess; they wrote a rigorous proof showing why this works.

The Acceleration Mechanism: They proved that NGMRES speeds things up by a specific "gain factor." Think of it as a turbo boost. If the old method was a bicycle, NGMRES is a motorcycle, and the size of the engine depends on how well the "shortcut" calculation works.
Saving the Divergent: In many cases where the standard method (Picard) gives up and says, "I can't solve this," NGMRES steps in and finds the solution anyway. It's like a rescue team that can navigate the fog where the original explorer got lost.
Sharp Predictions: They showed that their mathematical predictions of how fast the solution would converge were incredibly accurate. The theory matched the reality almost perfectly.

Real-World Tests

The team tested this on three scenarios:

A 2D Box (The Driven Cavity): Like air swirling in a square room. Here, the new method worked great, and the old ruler was okay, but the new one was better.
A 3D Box: Like air swirling in a cube. Here, the old ruler failed completely (the math broke down), but the new ruler solved it quickly.
A Stenotic Artery: A model of a narrowed blood vessel. This is a real-life medical application. The standard method took 45 steps to solve it; the new method took only 18.

The Bottom Line

This paper is a breakthrough because it's the first time anyone has mathematically proven exactly why this acceleration technique works for fluid dynamics and identified the correct "ruler" to use.

In simple terms: They figured out that to solve the complex math of moving fluids, you can't just use a generic calculator. You need a specialized tool that understands the unique physics of the fluid. Once you use that tool, you can solve problems that were previously impossible or took forever, making simulations for weather, planes, and medicine much faster and more reliable.

1. Problem Statement

The paper addresses the challenge of solving the steady-state Navier-Stokes equations (NSE) using the Picard iteration (a fixed-point iteration).

The Issue: While the Picard iteration is globally stable and linearly convergent for low Reynolds numbers ($Re$), its convergence rate deteriorates as $Re$ increases. For sufficiently high $Re$ (where the contraction constant $\kappa > 1$ ), the standard Picard iteration often fails to converge or diverges entirely.
The Goal: To accelerate the Picard iteration for NSE using Nonlinear GMRES (NGMRES), a technique that has not been rigorously analyzed for this specific application prior to this work. The authors aim to establish a convergence theory that explains why and how NGMRES accelerates the solution, and to identify the optimal mathematical norms for the underlying optimization problem.

2. Methodology

The authors propose applying NGMRES to the NSE Picard iteration and developing a rigorous convergence analysis based on the nonlinear residual rather than the fixed-point residual.

A. NGMRES Formulation

For a fixed-point operator $q(u)$ solving $g(u)=0$ , the NGMRES update at step $k+1$ with depth $m$ is:
$u_{k+1} = q(u_k) + \sum_{i=0}^{m_k} \beta_{k+1}^i (q(u_k) - u_{k-i})$
The coefficients $\beta$ are determined by solving a least-squares optimization problem.

Key Innovation: The authors formulate the optimization problem using the dual norm ( $V'$ ) of the divergence-free velocity space, rather than the standard $\ell_2$ norm used in most literature.
Residual Definition: The optimization minimizes the norm of the nonlinear residual $g(u) = -\nu\Delta u + u \cdot \nabla u - f$ .

B. Theoretical Framework

The analysis is conducted in the divergence-free velocity space $V \subset H^1_0(\Omega)$ and its dual $V'$ .

Optimization Gain: The authors define two key metrics:
- $\theta_{k+1}$ : The gain of the optimization relative to the previous iterate.
- $\gamma_{k+1}$ : The gain of the optimization relative to a single unaccelerated Picard step.
Convergence Bounds: They prove that the nonlinear residual satisfies:
$\|g(u_{k+1})\|_{V'} \leq \gamma_{k+1} \kappa \|g(u_k)\|_{V'} + O(\|g\|^2)$
$\|g(u_{k+1})\|_{V'} \leq \theta_{k+1} \|g(u_k)\|_{V'} + O(\|g\|^2)$
This demonstrates that the acceleration is driven by the reduction factor (gain) of the optimization problem, effectively scaling the Picard contraction constant $\kappa$ .

C. Norm Selection Analysis

A critical theoretical contribution is the analysis of the optimization norm:

2D: Using the $L^2$ (or $\ell_2$ ) norm is theoretically acceptable due to inverse inequalities, though $V'$ is still preferred.
3D: Using the $\ell_2$ norm is shown to be suboptimal and potentially divergent. The nonlinear term $u \cdot \nabla u$ does not reside in $L^2$ for 3D flows; it resides in $V'$ . Using $\ell_2$ introduces inverse inequality factors ( $h^{-1/2}$ ) that can dominate the error terms, preventing convergence as the mesh is refined.

3. Key Contributions

First Convergence Proof for NGMRES-Picard: This is the first paper to provide a convergence analysis for NGMRES applied to NSE Picard iteration that explicitly identifies the mechanism of acceleration (the optimization gain).
Identification of the Optimal Norm: The authors prove that the dual norm ( $V'$ ) is the mathematically correct choice for the least-squares optimization in the NSE context, particularly for 3D problems. They demonstrate analytically and numerically that using $\ell_2$ can lead to failure in 3D.
Sharp Convergence Estimates: The derived bounds are shown to be remarkably sharp. The theoretical gain factors ( $\theta_k, \gamma_k$ ) match the observed residual reduction ratios in numerical experiments once the residual is small.
Handling Divergent Cases: The method is shown to converge even in regimes where the unaccelerated Picard iteration diverges (high Reynolds numbers).

4. Numerical Results

The authors validated their theory using three benchmark problems:

2D Driven Cavity:
- Tested at $Re=5000$ and $10000$.
- Standard Picard failed to converge within 100 iterations at $Re=10000$.
- NGMRES with $V'$ norm achieved convergence in ~30–45 iterations.
- Theoretical bounds ( $\theta_k$ ) matched the actual residual reduction ratios almost perfectly after initial iterations.
- Norm Comparison: For $m=0,1$ , $V'$ was significantly better than $\ell_2$ . For larger $m$ , the difference diminished but $V'$ remained robust.
3D Driven Cavity:
- Tested at $Re=400$ and $1000$.
- Standard Picard diverged.
- NGMRES with $V'$ norm converged rapidly (e.g., 68 iterations for $Re=1000$ with $m=20$ ).
- Norm Comparison: Using $\ell_2$ as the optimization norm resulted in failure to converge (residuals plateaued at $10^{-4}$ to $10^{-5}$ ), confirming the theoretical prediction that $\ell_2$ is unsuitable for 3D NSE.
Stenotic Artery (3D):
- A complex geometry with high aspect ratios.
- NGMRES with $V'$ norm reduced iterations from ~45 (Picard) to ~18 ( $m=\infty$ ).
- NGMRES with $\ell_2$ norm failed to converge for all tested depths ( $m=0, 5, 10, \infty$ ).

5. Significance

Theoretical Advancement: The paper bridges a gap in nonlinear acceleration theory by moving beyond simple equivalence to GMRES (which applies to linear systems) to a specific analysis of nonlinear PDEs. It clarifies that the "gain" of the optimization problem is the driver of acceleration.
Practical Impact: It provides a robust, accelerated solver for high-Reynolds number Navier-Stokes problems where standard Picard iteration fails.
Norm Selection Guidance: The work serves as a critical warning for practitioners: applying standard $\ell_2$ -based NGMRES to 3D fluid dynamics problems may lead to divergence. The choice of the optimization norm must align with the functional space of the residual ( $V'$ for NSE).
Future Directions: The authors suggest comparing NGMRES with Anderson Acceleration (AA) for NSE and exploring convergence theories for NGMRES using $\ell_2$ norms in other problem settings.

In summary, this paper establishes NGMRES as a powerful, theoretically grounded acceleration technique for Navier-Stokes equations, provided the optimization is performed in the correct dual norm ( $V'$ ), ensuring convergence even in regimes where traditional methods fail.