Mathematical analysis

Sequence (biology)

Geometry

Linear system

Combinatorics

Physics

Generalized minimal residual method

Nonlinear system

Acceleration

Mathematics

Biology

Extrapolation

Rank (graph theory)

Quantum mechanics

Algorithm

Connection (principal bundle)

Classical mechanics

Polynomial

Applied mathematics

Genetics

SIAM Review

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.

Shanks Sequence Transformations and Anderson Acceleration