Abstract
This paper presents a general framework for Shanks transformations of sequences of elements in a vector space. It is shown that Minimal Polynomial Extrapolation (MPE), Modified Minimal Polynomial Extrapolation (MMPE), Reduced Rank Extrapolation (RRE), the Vector Epsilon Algorithm (VEA), the Topological Epsilon Algorithm (TEA), and Anderson Acceleration (AA), which are standard general techniques designed to accelerate arbitrary sequences and/or solve nonlinear equations, all fall into this framework. Their properties and their connections with quasi-Newton and Broyden methods are studied. The paper then exploits this framework to compare these methods. In the linear case, it is known that AA and GMRES are “essentially” equivalent in a certain sense, while GMRES and RRE are mathematically equivalent. This paper discusses the connection between AA, the RRE, the MPE, and other methods in the nonlinear case.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 646-669 |
| Number of pages | 24 |
| Journal | SIAM Review |
| Volume | 60 |
| Issue number | 3 |
| DOIs | |
| State | Published - 2018 |
Bibliographical note
Funding Information:∗Received by the editors March 13, 2017; accepted for publication (in revised form) November 20, 2017; published electronically August 8, 2018. http://www.siam.org/journals/sirev/60-3/M112072.html Funding: The work of the first author was supported in part by the Labex CEMPI (ANR-11-LABX-0007-01) and, in part, by the University of Padua. The work of the second author was partially supported by the University of Padua, Project 2014, CPDA143275. The work of the third author was supported by the Scientific Discovery through Advanced Computing (SciDAC) program funded by the U.S. Department of Energy, Office of Science, Advanced Scientific Computing Research and Basic Energy Sciences, grant DE-SC0008877.
Funding Information:
The work of the first author was supported in part by the Labex CEMPI (ANR-11LABX-0007-01) and, in part, by the University of Padua. The work of the second author was partially supported by the University of Padua, Project 2014, CPDA143275. The work of the third author was supported by the Scientific Discovery through Advanced Computing (SciDAC) program funded by the U.S. Department of Energy, Office of Science, Advanced Scientific Computing Research and Basic Energy Sciences, grant DE-SC0008877. We thank the reviewers for pointing out an error in a previous version of this paper. Their constructive comments encouraged us to expand this study and develop the general framework discussed here. C.B. would like to thank Prof. Yvon Maday for drawing his attention to AA. This work started as a result of a presentation made by Y.S. at the workshop Numerical Methods for Large-Scale Nonlinear Problems and Their Applications, held at ICERM (Providence, RI, USA) August 31 to September 4, 2015.
Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.
Keywords
- Acceleration techniques
- Anderson acceleration
- Broyden methods
- Quasi-Newton methods
- Reduced rank extrapolation
- Sequence transformations