🔢 mathematics

NGMRES convergence analysis and proof of acceleration for contractive and noncontractive iterations

This paper presents the first convergence analysis and proof of acceleration for nonlinear GMRES (NGMRES) applied to both contractive and noncontractive fixed point iterations, demonstrating that the optimization problem's ratio gain drives acceleration while a newly identified quantity accurately predicts linear convergence rates and guides adaptive depth selection.

Original authors: Y. He, L. Rebholz, M. Xiao

Published 2026-07-17

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Y. He, L. Rebholz, M. Xiao

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 find the perfect spot to park a car in a crowded, twisting garage. You have a map (a mathematical equation) that tells you where the empty spot is, but the map is tricky. Every time you move the car based on the map's instructions, you might overshoot, undershoot, or even drive in circles. This is a common problem in science and engineering: solving complex, non-linear puzzles where the answer isn't a straight line. Scientists use "fixed point iterations," which is just a fancy way of saying "guess, check, and repeat." You make a guess, see how far off you are, and adjust your next guess based on that error. Sometimes, this process works like a charm, slowly sliding the car into the spot. Other times, the car spins out of control, driving further and further away from the solution.

To fix this, mathematicians have developed "accelerators." Think of these as a co-pilot who looks at your last few moves and says, "Hey, you're zigging when you should be zagging. Let's try a shortcut." One famous co-pilot is called Anderson Acceleration. But there is another, slightly different one called Nonlinear GMRES (or NGMRES). For a long time, scientists knew these co-pilots worked well in practice, but they didn't have a solid rulebook explaining why they worked, especially when the parking garage was particularly chaotic (mathematically speaking, "non-contractive"). They also didn't know exactly how to tune the co-pilot for the best results.

This paper is the first to write that rulebook for NGMRES. The authors, Yunhui He, Leo G Rebholz, and Mengying Xiao, have proven mathematically that NGMRES works not just for easy problems, but for the hard, chaotic ones too. They discovered the secret sauce: a specific "gain" factor. Imagine this gain as a volume knob on your co-pilot's radio. If the knob is turned down (less than 1), the co-pilot successfully damps out the errors and speeds up the parking process. If the knob is stuck at 1, the co-pilot isn't helping. The paper proves that this gain is the engine behind the acceleration. Furthermore, they found a way to predict exactly how fast the car will park at any given moment. They also showed that while the other famous co-pilot (Anderson Acceleration) sometimes stumbles on super-fast solutions, NGMRES stays steady and doesn't slow things down.

The Story of the Smart Co-Pilot

So, how does this NGMRES co-pilot actually work? Let's go back to our parking garage. In a standard "fixed point iteration," you take a step, look at how far you are from the spot, and take another step. It's like walking forward, checking the distance, and taking another step. If the garage is slippery (non-contractive), you might slide backward.

NGMRES is smarter. Instead of just looking at your last step, it looks at your last few steps. It asks, "If I combine your last move, the one before that, and the one before that, can I find a better path?" It solves a little optimization problem (a mini-puzzle) to figure out the perfect mix of your past moves to get to the next spot. This mix is determined by coefficients (numbers) that the algorithm calculates on the fly.

The big breakthrough in this paper is proving that this mixing process has a "gain." The authors showed that the algorithm calculates a ratio (let's call it $\gamma$ ) that tells you how much better the new guess is compared to just taking a normal step. If this ratio is less than 1, you are accelerating. The paper proves that this gain is the only reason the method speeds things up. It's like the co-pilot saying, "I can cut the distance to the spot by 30% right now," and the math proves that this is exactly what's happening.

But there's a catch. The paper also introduces a second number, $\theta$ , which acts like a crystal ball. It predicts how fast you will converge in the next step. The authors found that this crystal ball is incredibly accurate. Once the car gets close to the spot (the "nonlinear residuals" get small), the prediction is spot-on. This is huge because it means you can use this number to decide how many past steps to look at. If the prediction is good, you can look at more steps to go faster. If it's shaky, you should look at fewer. The paper suggests an "adaptive strategy" where the algorithm changes its own settings based on this crystal ball, making it even more efficient.

When the Garage is a Nightmare

One of the most exciting parts of the paper is how it handles the "non-contractive" cases. These are the garages where the floor is so slippery that every time you try to move forward, you slide backward. Standard methods fail here. The paper proves that NGMRES can still work in these nightmares, but with a twist.

In these chaotic scenarios, the "higher-order terms" (the tiny, messy errors that accumulate) can become a problem. The authors show that if you keep the co-pilot looking at too many past steps for too long in a chaotic garage, those tiny errors can pile up and ruin the convergence. The solution? "Restarts." Imagine that after every 25 or 50 steps, you tell the co-pilot, "Forget the last 50 steps, let's start fresh with just the last few." The paper's simulations show that doing this dramatically improves convergence. Without restarts, the car might spin in circles; with restarts, it finds the spot.

The Battle of the Co-Pilots: NGMRES vs. Anderson

For years, scientists have debated which co-pilot is better: Anderson Acceleration (AA) or NGMRES. They both look at past steps, but they measure "error" differently. AA looks at the error in the instructions (the fixed point residuals), while NGMRES looks at the error in the actual map (the nonlinear residuals).

The paper settles a specific part of this debate. It shows that for "superlinear" iterations (where the car is already moving very fast and getting closer to the spot exponentially), Anderson Acceleration can actually slow you down. Why? Because AA's math introduces "higher-order terms" that are a bit messy and can reduce the speed of convergence. NGMRES, on the other hand, has "quadratic" higher-order terms, which are cleaner. The paper's simulations show that when you use NGMRES with a super-fast solver, it keeps the speed up, whereas AA drags it down. It's like AA is a co-pilot who starts giving too much advice when you're already driving perfectly, while NGMRES knows when to stay quiet and let you fly.

Testing the Theory in the Real World

The authors didn't just stop at math; they tested their theory on some very tough real-world problems.

The Laser Problem (Nonlinear Helmholtz): They simulated how light travels through special crystals (Kerr dielectrics). This is a notoriously hard problem where standard methods often fail. They found that using the "dual norm" (a specific way of measuring error that matches the physics of the problem) was crucial. If they used a simple, standard measurement (the $\ell_2$ norm), the method failed or was much slower. But with the correct "dual norm" measurement, the method converged quickly, even for very difficult settings. This confirms that the "ruler" you use to measure error matters just as much as the co-pilot itself.
The Hot Air Problem (Boussinesq Equations): They simulated air flowing in a 3D box with hot and cold sides. This is a classic fluid dynamics problem. Again, the standard method failed to converge for high temperatures (high Rayleigh numbers). But with NGMRES, using the adaptive depth strategy (changing how many past steps to look at based on the crystal ball prediction), they solved it in about 53 iterations. Without the adaptive strategy, it took much longer or failed entirely.
The Multiple Solutions Problem (Navier-Stokes): In some fluid problems, there isn't just one answer; there are five different ways the water can flow. Finding all of them is like finding five different parking spots in the same garage. The authors combined NGMRES with a "deflation" technique (a way to tell the algorithm, "We already found this spot, go find a new one"). They successfully found all distinct solutions for a channel expansion problem, something that usually requires a very slow, step-by-step process.
The Speed Test: Finally, they tested the superlinear claim. Using simple 1D math problems, they showed that NGMRES helped a standard solver get faster, while Anderson Acceleration actually made a super-fast solver slower.

The Takeaway

This paper is a major step forward because it moves NGMRES from a "black box" tool that works sometimes to a well-understood method with a clear rulebook. The authors have proven that the "gain" of the optimization problem is the engine of acceleration. They have identified a crystal ball ( $\theta$ ) that predicts convergence rates with high accuracy, allowing for smart, adaptive strategies. They have shown that "restarts" are essential for chaotic problems and that NGMRES is uniquely suited for super-fast solvers where other methods fail.

While the paper doesn't claim to have solved every nonlinear problem in the universe, it has provided the first rigorous proof that NGMRES accelerates both contractive and non-contractive iterations. It suggests that by using the right measurement tools (dual norms) and smart strategies (adaptive depth and restarts), we can solve some of the most stubborn mathematical puzzles in physics and engineering much faster than before. The door is now open for engineers and scientists to tune their co-pilots with confidence, knowing exactly how and why they work.

Technical Summary: NGMRES Convergence Analysis and Proof of Acceleration for Contractive and Noncontractive Iterations

Problem Statement
This paper addresses the convergence analysis and acceleration mechanisms of Nonlinear GMRES (NGMRES) when applied to general nonlinear systems $g(x) = 0$ . While NGMRES has been utilized since 1997 to accelerate fixed-point iterations (FPIs) for various applications (e.g., Navier-Stokes equations, image restoration, tensor decomposition), a rigorous theoretical proof of its acceleration capabilities for general nonlinear systems—specifically covering both contractive and noncontractive iterations—was previously lacking. Existing theories were either limited to specific contractive cases (such as the steady Navier-Stokes equations with Picard iteration under small data assumptions) or focused on Anderson Acceleration (AA), which uses fixed-point residuals rather than the true nonlinear residuals utilized by NGMRES.

Methodology
The authors develop a single-step convergence analysis for NGMRES applied to a fixed-point operator $q(x)$ where $x_{k+1} = q(x_k)$ . The NGMRES update at iteration $k+1$ is formulated as a constrained optimization problem:
$x_{k+1} = \alpha_{k+1}^{k+1}q(x_k) + \sum_{j=k-m_k}^{k} \alpha_{k+1}^j x_j$
where the coefficients $\alpha$ minimize the norm of the nonlinear residual combination:
$\min_{\sum \alpha = 1} \left\| \alpha_{k+1}^{k+1}g(q(x_k)) + \sum_{j=k-m_k}^{k} \alpha_{k+1}^j g(x_j) \right\|_{H'}$
Crucially, the analysis requires the optimization norm to be the range norm of $g$ (the dual norm $H'$ ), rather than the historically common $\ell_2$ norm. The authors assume $g$ is Lipschitz continuously Fréchet differentiable and $q$ is continuous, satisfying specific bounds relating fixed-point residuals to nonlinear residuals. The analysis distinguishes between:

Depth $m=0$ : A base case applicable to both contractive and noncontractive iterations.
General depth $m \ge 1$ : Analyzed separately for contractive (Lipschitz constant $\kappa_q < 1$ ) and noncontractive cases.

Key Contributions
The paper provides the first theoretical proof that NGMRES accelerates convergence for general nonlinear systems in both contractive and noncontractive regimes. The primary contributions include:

Identification of the Acceleration Mechanism: The analysis identifies the "gain of the optimization problem," denoted as $\gamma_{k+1}^m$ , as the specific mechanism responsible for acceleration. The nonlinear residual bound is shown to scale the linear convergence rate $\kappa$ of the unaccelerated FPI by this gain:
$\|g(x_{k+1})\|_{H'} \le \gamma_{k+1}^m \kappa \|g(x_k)\|_{H'} + \text{higher order terms}$
Since $\gamma_{k+1}^m \le 1$ (and typically $<1$ ), this scaling reduces the linear convergence rate.
Prediction of Linear Convergence Rate: A second quantity, $\theta_{k+1}^m$ , is introduced which directly approximates the linear convergence rate at each step. The analysis proves $\theta_{k+1}^m \le 1$ , establishing that NGMRES reduces the nonlinear residual (up to higher-order terms). The paper demonstrates that $\theta_{k+1}^m$ is a remarkably accurate predictor of the actual convergence rate once higher-order terms become negligible.
Analysis of Noncontractive Iterations: For noncontractive cases with $m \ge 1$ , the authors show that higher-order terms depend on the entire history of iterations and are scaled by a coefficient that grows with $k$ . This suggests that without intervention, higher-order terms could dominate and prevent convergence. Consequently, the authors propose and validate the use of restarts to mitigate this effect.
Comparison with Anderson Acceleration (AA): The paper highlights theoretical and practical differences between NGMRES and AA. Specifically, NGMRES uses nonlinear residuals (vs. fixed-point residuals in AA) and, for depth 1, possesses quadratic higher-order terms (vs. order 1.62 for AA). This suggests NGMRES is better suited for superlinearly converging iterations, whereas AA can degrade superlinear convergence.
Norm Selection: The theory necessitates the use of the range norm of $g$ (dual norm) for the optimization problem. Numerical tests confirm that while $\ell_2$ may suffice for easier problems, the dual norm yields significantly better convergence for challenging, highly anisotropic, or stiff problems.

Numerical Results
The theoretical findings are validated through four numerical experiments:

Nonlinear Helmholtz Equation: Demonstrates that NGMRES enables convergence for Picard iterations that diverge without acceleration. It validates the accuracy of $\theta_k$ as a predictor and shows that restarts significantly improve convergence in noncontractive regimes (e.g., $k_0=40$ ). It further confirms that using the dual norm ( $H'$ ) yields convergence where $\ell_2$ fails for difficult cases ( $k_0=60$ ).
3D Buoyancy Driven Flow (Boussinesq Equations): Shows NGMRES accelerating convergence for Rayleigh numbers where Picard iteration fails. It illustrates the effectiveness of an adaptive depth strategy that increases $m$ when $\theta_k$ accurately predicts the convergence rate (indicating higher-order terms are negligible), leading to faster convergence than fixed-depth approaches.
Incompressible Navier-Stokes (Channel Expansion): Demonstrates NGMRES combined with deflation techniques to find multiple distinct solutions of a multi-solution PDE directly at high Reynolds numbers, avoiding slow continuation methods.
Superlinear Iterations (Newton/Secant): A 1D test comparing $m=0$ NGMRES and depth-1 AA on superlinear iterations. Results show NGMRES improves convergence without degrading the superlinear asymptotic rate, whereas AA slows down the convergence.

Significance
The paper claims to fill a critical gap in NGMRES theory by providing a general proof of acceleration for both contractive and noncontractive fixed-point iterations. It moves beyond specific case studies to establish a general framework where the "gain of the optimization problem" is the driver of acceleration. The work provides practical tools for practitioners, including the use of $\theta_k$ for adaptive depth selection and the necessity of restarts for noncontractive problems. Furthermore, it offers a theoretical basis for preferring NGMRES over AA in scenarios involving superlinear iterations or problems requiring the minimization of true nonlinear residuals, while emphasizing the importance of selecting the correct optimization norm (dual norm) for robust performance.

The Story of the Smart Co-Pilot

When the Garage is a Nightmare

The Battle of the Co-Pilots: NGMRES vs. Anderson

Testing the Theory in the Real World

The Takeaway

More like this