Shanks sequence transformations and anderson acceleration

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.