Anderson
Anderson Acceleration for Fixed-Point Iterations. This paper concerns an acceleration method for fixed-point iterations that originated in work of D. G. Anderson [J. Assoc. Comput. Mach., 12 (1965), pp. 547–560], which we accordingly call Anderson acceleration here. This method has enjoyed considerable success and wide usage in electronic structure computations, where it is known as Anderson mixing; however, it seems to have been untried or underexploited in many other important applications. Moreover, while other acceleration methods have been extensively studied by the mathematics and numerical analysis communities, this method has received relatively little attention from these communities over the years. A recent paper by H. Fang and Y. Saad [Numer. Linear Algebra Appl., 16 (2009), pp. 197–221] has clarified a remarkable relationship of Anderson acceleration to quasi-Newton (secant updating) methods and extended it to define a broader Anderson family of acceleration methods. In this paper, our goals are to shed additional light on Anderson acceleration and to draw further attention to its usefulness as a general tool. We first show that, on linear problems, Anderson acceleration without truncation is “essentially equivalent” in a certain sense to the generalized minimal residual (GMRES) method. We also show that the Type 1 variant in the Fang–Saad Anderson family is similarly essentially equivalent to the Arnoldi (full orthogonalization) method. We then discuss practical considerations for implementing Anderson acceleration and illustrate its performance through numerical experiments involving a variety of applications.
Keywords for this software
References in zbMATH (referenced in 53 articles )
Showing results 1 to 20 of 53.
Sorted by year (- Ernesti, Felix; Schneider, Matti; Böhlke, Thomas: Fast implicit solvers for phase-field fracture problems on heterogeneous microstructures (2020)
- Evans, Claire; Pollock, Sara; Rebholz, Leo G.; Xiao, Mengying: A proof that Anderson acceleration improves the convergence rate in linearly converging fixed-point methods (but not in those converging quadratically) (2020)
- Anderson, Donald G. M.: Comments on: “Anderson acceleration, mixing and extrapolation” (2019)
- Brezinski, Claude; Redivo-Zaglia, Michela: The genesis and early developments of Aitken’s process, Shanks’ transformation, the (\varepsilon)-algorithm, and related fixed point methods (2019)
- Brezinski, Claude; Redivo-Zaglia, Michela: Extrapolation methods for the numerical solution of nonlinear Fredholm integral equations (2019)
- Chen, Xiaojun; Kelley, C. T.: Convergence of the EDIIS algorithm for nonlinear equations (2019)
- Dolejší, Vít; Kuraz, Michal; Solin, Pavel: Adaptive higher-order space-time discontinuous Galerkin method for the computer simulation of variably-saturated porous media flows (2019)
- Jiang, Jiamin; Tchelepi, Hamdi A.: Nonlinear acceleration of sequential fully implicit (SFI) method for coupled flow and transport in porous media (2019)
- Ji, Hangjie; Li, Longfei: Numerical methods for thermally stressed shallow shell equations (2019)
- Li, Zhizhi; Chu, Risheng; Zhang, Huai: Accelerating the shift-splitting iteration algorithm (2019)
- Pollock, Sara; Rebholz, Leo G.; Xiao, Mengying: Anderson-accelerated convergence of Picard iterations for incompressible Navier-Stokes equations (2019)
- Barrenechea, Gabriel R.; John, Volker; Knobloch, Petr; Rankin, Richard: A unified analysis of algebraic flux correction schemes for convection-diffusion equations (2018)
- Bormetti, G.; Callegaro, G.; Livieri, G.; Pallavicini, A.: A backward Monte Carlo approach to exotic option pricing (2018)
- Brezinski, Claude; Redivo-Zaglia, Michela; Saad, Yousef: Shanks sequence transformations and Anderson acceleration (2018)
- Cai, Yunfeng; Zhang, Lei-Hong; Bai, Zhaojun; Li, Ren-Cang: On an eigenvector-dependent nonlinear eigenvalue problem (2018)
- Garrett, C. Kristopher; Hauck, Cory D.: A fast solver for implicit integration of the Vlasov-Poisson system in the Eulerian framework (2018)
- Kelley, C. T.: Numerical methods for nonlinear equations (2018)
- Martini dos Santos, Tiara; Reips, Louise; Martínez, José Mario: Under-relaxed quasi-Newton acceleration for an inverse fixed-point problem coming from positron emission tomography (2018)
- Mergia, Woinshet D.; Patidar, Kailash C.: Fractional-step (\theta)-method for solving singularly perturbed problem in ecology (2018)
- Peherstorfer, Benjamin; Willcox, Karen; Gunzburger, Max: Survey of multifidelity methods in uncertainty propagation, inference, and optimization (2018)