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 18 articles )
Showing results 1 to 18 of 18.
Sorted by year (- Barrenechea, Gabriel R.; John, Volker; Knobloch, Petr: Analysis of algebraic flux correction schemes (2016)
- De Sterck, Hans; Howse, Alexander: Nonlinearly preconditioned optimization on Grassmann manifolds for computing approximate Tucker tensor decompositions (2016)
- Hamilton, Steven; Berrill, Mark; Clarno, Kevin; Pawlowski, Roger; Toth, Alex; Kelley, C.T.; Evans, Thomas; Philip, Bobby: An assessment of coupling algorithms for nuclear reactor core physics simulations (2016)
- Higham, Nicholas J.; Strabić, Nataša: Anderson acceleration of the alternating projections method for computing the nearest correlation matrix (2016)
- Loffeld, John; Woodward, Carol S.: Considerations on the implementation and use of Anderson acceleration on distributed memory and GPU-based parallel computers (2016)
- Brune, Peter R.; Knepley, Matthew G.; Smith, Barry F.; Tu, Xuemin: Composing scalable nonlinear algebraic solvers (2015)
- Deckelnick, Klaus; Katz, Jakob; Schieweck, Friedhelm: A $C^1$-finite element method for the Willmore flow of two-dimensional graphs (2015)
- De Sterck, Hans; Winlaw, Manda: A nonlinearly preconditioned conjugate gradient algorithm for rank-$R$ canonical tensor approximation. (2015)
- Toth, Alex; Kelley, C.T.: Convergence analysis for Anderson acceleration (2015)
- Botchev, M.A.; Oseledets, I.V.; Tyrtyshnikov, E.E.: Iterative across-time solution of linear differential equations: Krylov subspace versus waveform relaxation (2014)
- Bruss, Don E.; Morel, Jim E.; Ragusa, Jean C.: $S_2SA$ preconditioning for the $S_n$ equations with strictly nonnegative spatial discretization (2014)
- Willert, Jeffrey; Taitano, William T.; Knoll, Dana: Leveraging Anderson acceleration for improved convergence of iterative solutions to transport systems (2014)
- De Sterck, Hans: Steepest descent preconditioning for nonlinear GMRES optimization. (2013)
- John, Volker; Novo, Julia: On (essentially) non-oscillatory discretizations of evolutionary convection-diffusion equations (2012)
- Kuzmin, Dmitri: Linearity-preserving flux correction and convergence acceleration for constrained Galerkin schemes (2012)
- Kuzmin, Dmitri; Gorb, Yuliya: A flux-corrected transport algorithm for handling the close-packing limit in dense suspensions (2012)
- Augustin, Matthias; Caiazzo, Alfonso; Fiebach, André; Fuhrmann, Jürgen; John, Volker; Linke, Alexander; Umla, Rudolf: An assessment of discretizations for convection-dominated convection-diffusion equations (2011)
- Walker, Homer F.; Ni, Peng: Anderson acceleration for fixed-point iterations (2011)