Convergence Analysis for Nonlinear GMRES
Authors: Yunhui He
Abstract
In this work, we revisit nonlinear generalized minimal residual method (NGMRES) applied to nonlinear problems. NGMRES is used to accelerate the convergence of fixed-point iterations, which can substantially improve the performance of the underlying fixed-point iterations. We consider NGMRES with a finite window size $m$, denoted as NGMRES($m$). However, there is no convergence analysis for NGMRES($m$) applied to nonlinear systems. We prove that for general $m>0$, the residuals of NGMRES($m$) converge r-linearly under some conditions. For $m=0$, we prove that the residuals of NGMRES(0) converge q-linearly.
The papers around it, by date and closeness
Higher is closer to this paper; left is older. Lines join papers close to each other: groups of lines are sub-topics. Select a point to see why it is there. Back to the summary of this paper
Papers around this one
Ranked by how close their title and abstract are to this paper’s. Select some to read them together.
Closest papers
-
Convergence Analysis of an Alternating Nonlinear GMRES on Linear SystemsYun-Hui He · 2025 · Numerical Linear Algebra with Applications · cited 7 times · Not summarized yet
Abstract
In this work, we develop an alternating nonlinear Generalized Minimum Residual (NGMRES) algorithm with depth m$$ m $$ and periodicity p$$ p $$ , denoted by aNGMRES( m,p$$ m,p $$ ), applied to linear systems. We provide a theoretical analysis to quantify by how much one‐step NGMRES( m$$ m $$ ) using Richardson iterations as initial guesses can improve the convergence speed of the underlying fixed‐point iteration for diagonalizable and symmetric positive definite cases. Our theoretical analysis gives us a better understanding of which factors affect the convergence speed. Moreover, under certain conditions, we prove the periodic equivalence between the proposed aNGMRES applied to Richardson it…
-
NGMRES convergence analysis and proof of acceleration for contractive and noncontractive iterationsY. He, L. Rebholz, M. Xiao · 2026 · arXiv.org · preprint, not peer reviewed · Not summarized yet
Abstract
This paper gives the first convergence analysis and proof of acceleration for nonlinear GMRES (NGMRES) applied to contractive and noncontractive fixed point iterations (FPIs) for solving general nonlinear systems. Our main results are that in both the contractive and noncontractive cases, the ratio gain of the optimization problem is the mechanism responsible for accelerating (or enabling) convergence. Our analysis also reveals a second important quantity related to the optimization problem, which directly predicts the linear convergence rate at each iteration and proves it is at most 1; hence only higher order terms are responsible for NGMRES non-convergence. Numerical results for several c…
-
On the Asymptotic Linear Convergence Speed of Anderson Acceleration, Nesterov Acceleration, and Nonlinear GMRESH. De Sterck, Yun-Hui He · 2020 · SIAM Journal on Scientific Computing · cited 42 times · Not summarized yet
Abstract
We consider nonlinear convergence acceleration methods for fixed-point iteration $x_{k+1}=q(x_k)$, including Anderson acceleration (AA), nonlinear GMRES (NGMRES), and Nesterov-type acceleration (corresponding to AA with window size one). We focus on fixed-point methods that converge asymptotically linearly with convergence factor $\rho<1$ and that solve an underlying fully smooth and non-convex optimization problem. It is often observed that AA and NGMRES substantially improve the asymptotic convergence behavior of the fixed-point iteration, but this improvement has not been quantified theoretically. We investigate this problem under simplified conditions. First, we consider stationary versi…
-
Convergence analysis and proof of acceleration for NGMRES applied to the Picard iteration for Navier-Stokes equationsYun-Hui He, L. Rebholz · 2026 · arXiv.org · preprint, not peer reviewed · cited 3 times · Not summarized yet
Abstract
We consider nonlinear GMRES (NGMRES) as an acceleration technique for the Navier-Stokes Picard iteration, a direction that has not previously been explored. We identify the optimal norm for the least squares optimization problem arising in the NGMRES algorithm, and establish a convergence analysis for NGMRES with general depth that proves NGMRES scales the Picard Lipschitz constant by the gain of the optimization problem. To our knowledge, this is the first convergence proof for NGMRES that identifies the mechanism responsible for convergence acceleration. Numerical experiments demonstrate that the convergence estimates are remarkably sharp. In addition, NGMRES greatly improves the performan…
-
Properties of Nonlinear GMRES Applied to the Preconditioned Richardson IterationYunhui He · 2026 · arXiv.org · preprint, not peer reviewed · cited 4 times · Not summarized yet
Abstract
In this work, we propose new variants of Anderson acceleration and nonlinear GMRES for general fixed-point iterations, based on modified least-squares problems associated with the methods. To solve the underlying linear systems, we apply these new approaches to accelerate the preconditioned Richardson iteration. We establish connections between the proposed variants and both left- and right-preconditioned GMRES. In particular, we show that full NGMRES applied to the preconditioned Richardson iteration is equivalent to right-preconditioned GMRES, while full NGMRES equipped with the new least-squares formulation is equivalent to left-preconditioned GMRES. Furthermore, under certain conditions …
-
Steepest descent preconditioning for nonlinear GMRES optimizationH. De Sterck · 2011 · Numerical Linear Algebra with Applications · cited 37 times · Not summarized yet
Abstract
Steepest descent preconditioning is considered for the recently proposed nonlinear generalized minimal residual (N‐GMRES) optimization algorithm for unconstrained nonlinear optimization. Two steepest descent preconditioning variants are proposed. The first employs a line search, whereas the second employs a predefined small step. A simple global convergence proof is provided for the N‐GMRES optimization algorithm with the first steepest descent preconditioner (with line search), under mild standard conditions on the objective function and the line search processes. Steepest descent preconditioning for N‐GMRES optimization is also motivated by relating it to standard non‐preconditioned GMRES …
-
A generalized alternating NGMRES method for PDE-constrained optimization problems governed by transport equationsYun-Hui He, Andreas Mang · 2025 · cited 4 times · Not summarized yet
Abstract
In this work, we propose a generalized alternating nonlinear generalized minimal residual method (GA-NGMRES) to accelerate first-order optimization schemes for PDE-constrained optimization problems governed by transport equations. We apply GA-NGMRES to a preconditioned first-order optimization scheme by interpreting the update rule as a fixed-point (FP) iteration. Our approach introduces a novel periodic mixing strategy that integrates NGMRES updates with FP steps. This new scheme improves efficiency in terms of both iteration count and runtime compared to the state-of-the-art. We include a comparison to first-order preconditioned gradient descent and preconditioned, inexact Gauss--Newton--K…
-
A Hybrid GMRES Algorithm for Nonsymmetric Linear SystemsN. Nachtigal, L. Reichel, L. Trefethen · 1992 · SIAM Journal on Matrix Analysis and Applications · cited 164 times · Not summarized yet
Prior work it builds on
-
A Nonlinear GMRES Optimization Algorithm for Canonical Tensor DecompositionH. De Sterck · 2011 · SIAM Journal on Scientific Computing · cited 75 times · Not summarized yet
Abstract
A new algorithm is presented for computing a canonical rank-R tensor approximation that has minimal distance to a given tensor in the Frobenius norm, where the canonical rank-R tensor consists of the sum of R rank-one components. Each iteration of the method consists of three steps. In the first step, a tentative new iterate is generated by a stand-alone one-step process, for which we use alternating least squares (ALS). In the second step, an accelerated iterate is generated by a nonlinear generalized minimal residual (GMRES) approach, recombining previous iterates in an optimal way, and essentially using the stand-alone one-step process as a preconditioner. In particular, the nonlinear ext…
-
Some observations on weighted GMRESS. Güttel, J. Pestana · 2014 · Numerical Algorithms · cited 32 times · Not summarized yet
-
GMRESR: a family of nested GMRES methodsH. A. van der Vorst, C. Vuik · 1994 · Numerical Linear Algebra with Applications · cited 370 times · Not summarized yet
-
Flexible GMRES with Deflated RestartingL. Giraud, S. Gratton, X. Pinel et al. · 2010 · SIAM Journal on Scientific Computing · cited 70 times · Not summarized yet
-
Convergence Analysis for Anderson AccelerationA. Toth, Carl Tim Kelley · 2015 · SIAM Journal on Numerical Analysis · cited 251 times · Not summarized yet
Go further
How are these papers found?
We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.
Updated on 1 November 2026.