A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)
From MaRDI portal
Publication:5217606
DOI10.1137/19M1245384zbMATH Open1433.65102arXiv1810.08455OpenAlexW3007299075MaRDI QIDQ5217606FDOQ5217606
Sara Pollock, Leo G. Rebholz, Mengying Xiao, Claire Evans
Publication date: 25 February 2020
Published in: SIAM Journal on Numerical Analysis (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1810.08455
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
- Convergence analysis of Anderson-type acceleration of Richardson's iteration.
Numerical solutions to equations with nonlinear operators (65J15) Extrapolation to the limit, deferred corrections (65B05)
Cites Work
- The \texttt{deal.II} library, version 8.4
- Two classes of multisecant methods for nonlinear acceleration
- Anderson acceleration of the alternating projections method for computing the nearest correlation matrix
- Anderson Acceleration for Fixed-Point Iterations
- Iterative Procedures for Nonlinear Integral Equations
- Introduction to the numerical analysis of incompressible viscous flows.
- Numerical investigation on the stability of singular driven cavity flow
- Convergence Analysis for Anderson Acceleration
- Convergence acceleration during the 20th century
- An assessment of coupling algorithms for nuclear reactor core physics simulations
- Composing scalable nonlinear algebraic solvers
- Anderson acceleration and application to the three-temperature energy equations
- Anderson-Accelerated Convergence of Picard Iterations for Incompressible Navier--Stokes Equations
- Numerical methods for nonlinear equations
- Considerations on the Implementation and Use of Anderson Acceleration on Distributed Memory and GPU-based Parallel Computers
Cited In (49)
- Anderson acceleration with truncated Gram-Schmidt
- Anderson acceleration for nonlinear PDEs discretized by space-time spectral methods
- Anderson Acceleration for Nonsmooth Fixed Point Problems
- Performance of acceleration techniques for staggered phase-field solutions
- Superlinear convergence of Anderson accelerated Newton's method for solving stationary <scp>Navier–Stokes</scp> equations
- Acceleration of nonlinear solvers for natural convection problems
- Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
- Anderson Acceleration for a Class of Nonsmooth Fixed-Point Problems
- Determining the nonlinearity in an acoustic wave equation
- Improved convergence of the Arrow-Hurwicz iteration for the Navier-Stokes equation via grad-div stabilization and Anderson acceleration
- 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
- Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point Analysis
- Anderson Accelerated Douglas--Rachford Splitting
- Non-stationary Anderson acceleration with optimized damping
- The effect of Anderson acceleration on superlinear and sublinear convergence
- 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
- An inverse potential problem for subdiffusion: stability and reconstruction*
- Enhancing electrical impedance tomography reconstruction using learned half-quadratic splitting networks with Anderson acceleration
- 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 as a Krylov method with application to convergence analysis
- Nonmonotone globalization for Anderson acceleration via adaptive regularization
- A robust solution strategy for the Cahn-Larché equations
- 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
- Filtering for Anderson Acceleration
- Anderson accelerating the preconditioned modulus approach for linear complementarity problems on second-order cones
- On the Asymptotic Linear Convergence Speed of Anderson Acceleration, Nesterov Acceleration, and Nonlinear GMRES
- Composite Anderson acceleration method with two window sizes and optimized damping
- Benchmarking results for the Newton-Anderson method
- 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
- Asymptotic convergence analysis and influence of initial guesses on composite Anderson acceleration
- An accelerated staggered scheme for variational phase-field models of brittle fracture
- Analysis of a New Implicit Solver for a Semiconductor Model
- 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 Acceleration of Nonlinear Solvers for the Stationary Gross-Pitaevskii Equation
- Anderson-accelerated polarization schemes for fast Fourier transform-based computational homogenization
- Efficient and effective algebraic splitting‐based solvers for nonlinear saddle point problems
- Anderson acceleration for partially observable Markov decision processes: a maximum entropy approach
- Enabling convergence of the iterated penalty Picard iteration with \(O ( 1 )\) penalty parameter for incompressible Navier-Stokes via Anderson acceleration
- nlTGCR: A Class of Nonlinear Acceleration Procedures Based on Conjugate Residuals
Uses Software
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)
