A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)
From MaRDI portal
(Redirected from Publication:5217606)
Abstract: This paper provides the first proof that Anderson acceleration (AA) improves the convergence rate of general fixed point iterations. AA has been used for decades to speed up nonlinear solvers in many applications, however a rigorous mathematical justification of the improved convergence rate has remained lacking. The key ideas of the analysis presented here are relating the difference of consecutive iterates to residuals based on performing the inner-optimization in a Hilbert space setting, and explicitly defining the gain in the optimization stage to be the ratio of improvement over a step of the unaccelerated fixed point iteration. The main result we prove is that AA improves the convergence rate of a fixed point iteration to first order by a factor of the gain at each step. In addition to improving the convergence rate, our results indicate that AA increases the radius of convergence. Lastly, our estimate shows that while the linear convergence rate is improved, additional quadratic terms arise in the estimate, which shows why AA does not typically improve convergence in quadratically converging fixed point iterations. Results of several numerical tests are given which illustrate the theory.
Recommendations
- Anderson acceleration for a class of nonsmooth fixed-point problems
- Anderson Acceleration for Nonsmooth Fixed Point Problems
- Anderson acceleration for fixed-point iterations
- On the asymptotic linear convergence speed of Anderson acceleration applied to ADMM
- A characterization of the behavior of the Anderson acceleration on linear problems
- On the asymptotic linear convergence speed of Anderson acceleration, Nesterov acceleration, and nonlinear GMRES
- Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
- The effect of Anderson acceleration on superlinear and sublinear convergence
- scientific article; zbMATH DE number 4137236
- Convergence analysis of Anderson-type acceleration of Richardson's iteration.
Cites work
- An assessment of coupling algorithms for nuclear reactor core physics simulations
- Anderson acceleration and application to the three-temperature energy equations
- Anderson acceleration for fixed-point iterations
- Anderson acceleration of the alternating projections method for computing the nearest correlation matrix
- Anderson-accelerated convergence of Picard iterations for incompressible Navier-Stokes equations
- Composing scalable nonlinear algebraic solvers
- Considerations on the Implementation and Use of Anderson Acceleration on Distributed Memory and GPU-based Parallel Computers
- Convergence acceleration during the 20th century
- Convergence analysis for Anderson acceleration
- Introduction to the numerical analysis of incompressible viscous flows.
- Iterative Procedures for Nonlinear Integral Equations
- Numerical investigation on the stability of singular driven cavity flow
- Numerical methods for nonlinear equations
- The \texttt{deal.II} library, version 8.4
- Two classes of multisecant methods for nonlinear acceleration
Cited in
(68)- Local improvement results for Anderson acceleration with inaccurate function evaluations
- Anderson acceleration preconditioned tensor splitting approach for tensor absolute value equation
- Anderson acceleration of the proximal point method: the exact adaptive minimax, a spectral phase transition, and optimal safeguarding
- nlTGCR: A Class of Nonlinear Acceleration Procedures Based on Conjugate Residuals
- Anderson acceleration for nonlinear PDEs discretized by space-time spectral methods
- Acceleration of nonlinear solvers for natural convection problems
- Anderson Acceleration for Nonsmooth Fixed Point Problems
- Performance of acceleration techniques for staggered phase-field solutions
- Leveraging Anderson acceleration for improved convergence of iterative solutions to transport systems
- Superlinear convergence of Anderson accelerated Newton's method for solving stationary <scp>Navier–Stokes</scp> equations
- Improved convergence of the Arrow-Hurwicz iteration for the Navier-Stokes equation via grad-div stabilization and Anderson acceleration
- Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
- Determining the nonlinearity in an acoustic wave equation
- On the asymptotic linear convergence speed of Anderson acceleration, Nesterov acceleration, and nonlinear GMRES
- Acceleration methods for fixed-point iterations
- Finite element iterative algorithm based on Anderson acceleration technique for incompressible MHD equations
- Newton-Anderson at Singular Points
- Anderson acceleration of gradient methods with energy for optimization problems
- Anderson acceleration for fixed-point iterations
- Anderson Accelerated Douglas--Rachford Splitting
- Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point Analysis
- Reconstruction of space-dependence and nonlinearity of a reaction term in a subdiffusion equation
- Non-stationary Anderson acceleration with optimized damping
- The effect of Anderson acceleration on superlinear and sublinear convergence
- Analysis of a new implicit solver for a semiconductor model
- A simple-to-implement nonlinear preconditioning of Newton's method for solving the steady Navier-Stokes equations
- Anderson acceleration of nonlinear solvers for the stationary Gross-Pitaevskii equation
- Secant Acceleration of Sequential Residual Methods for Solving Large-Scale Nonlinear Systems of Equations
- On an improved PDE-based elliptic parameterization method for isogeometric analysis using preconditioned Anderson acceleration
- Accelerating and enabling convergence of nonlinear solvers for Navier-Stokes equations by continuous data assimilation
- Anderson acceleration for a class of nonsmooth fixed-point problems
- Anderson acceleration for degenerate and nondegenerate problems
- Three Anderson accelerated iterative methods for solving large scale linear equations
- Enhancing electrical impedance tomography reconstruction using learned half-quadratic splitting networks with Anderson acceleration
- New time integrators and capabilities in SUNDIALS versions 6.2.0--7.4.0
- Descent Properties of an Anderson Accelerated Gradient Method with Restarting
- An adaptive solution strategy for Richards' equation
- Weighted Time-Semidiscretization Quasilinearization Method for Solving Rihards’ Equation
- A simple extrapolation method for clustered eigenvalues
- Anderson acceleration with truncated Gram-Schmidt
- On the asymptotic linear convergence speed of Anderson acceleration applied to ADMM
- A robust solution strategy for the Cahn-Larché equations
- Anderson acceleration as a Krylov method with application to convergence analysis
- Nonmonotone globalization for Anderson acceleration via adaptive regularization
- Anderson-Picard based nonlinear preconditioning of the Newton iteration for non-isothermal flow simulations
- Anderson acceleration based on the \(\mathcal{H}^{- s}\) Sobolev norm for contractive and noncontractive fixed-point operators
- One-step convergence of inexact Anderson acceleration for contractive and non-contractive mappings
- A gradient-based and determinant-free framework for fully Bayesian Gaussian process regression
- Filtering for Anderson Acceleration
- Benchmarking results for the Newton-Anderson method
- Anderson accelerating the preconditioned modulus approach for linear complementarity problems on second-order cones
- Composite Anderson acceleration method with two window sizes and optimized damping
- Generalized modulus-based matrix splitting algorithm with Anderson acceleration strategy for vertical linear complementarity problems
- Robust conservative scheme and nonlinear solver for phase transitions in heterogeneous permafrost
- A characterization of the behavior of the Anderson acceleration on linear problems
- Convergence analysis for Anderson acceleration
- An accelerated staggered scheme for variational phase-field models of brittle fracture
- Asymptotic convergence analysis and influence of initial guesses on composite Anderson acceleration
- Some theoretical results on the finite convergence property and the temporary stalling behavior of Anderson acceleration on linear systems
- Analysis of the Picard-Newton iteration for the Navier-Stokes equations: global stability and quadratic convergence
- An inverse potential problem for subdiffusion: stability and reconstruction
- Vector sequence acceleration algorithms for the INDSCAL model in multidimensional scaling analysis
- Numerical methods for fully nonlinear and related PDEs. Abstracts from the workshop held June 27 -- July 3, 2021 (hybrid meeting)
- Convergence analysis of adaptive DIIS algorithms with application to electronic ground state calculations
- Anderson-accelerated polarization schemes for fast Fourier transform-based computational homogenization
- Efficient and effective algebraic splitting‐based solvers for nonlinear saddle point problems
- Enabling convergence of the iterated penalty Picard iteration with O ( 1 ) penalty parameter for incompressible Navier-Stokes via Anderson acceleration
- Anderson acceleration for partially observable Markov decision processes: a maximum entropy approach
This page was built for publication: A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5217606)
