NGMRES convergence analysis and proof of acceleration for contractive and noncontractive iterations
For researchers using fixed point iterations to solve nonlinear systems, this work offers a theoretical foundation and practical guidance for accelerating convergence with NGMRES.
This paper provides the first convergence analysis and proof of acceleration for nonlinear GMRES (NGMRES) applied to both contractive and noncontractive fixed point iterations. It identifies the ratio gain of the optimization problem as the mechanism for acceleration and introduces a quantity that accurately predicts linear convergence rates, with numerical results showing improved convergence and advantages over Anderson acceleration.
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 challenging nonlinear test problems are given that illustrate the theory, show how the acceleration improves convergence, show that the quantity predicting the linear convergence rate is remarkably accurate and moreover can be useful for adaptively choosing NGMRES depth, show how restarts can improve convergence in noncontractive iterations, show how NGMRES is naturally suited for finding distinct solutions of a multi-solution PDE, and that NGMRES can perform better than Anderson acceleration when applied to superlinear FPIs.