Review of two vector extrapolation methods of polynomial type with applications to large-scale problems

An important problem that arises in different areas of science and engineering is that of computing limits of sequences of vectors {xn}, where xn∈CN with N very large. Such sequences arise, for example, in the solution of systems of linear or nonlinear equations by fixed-point iterative methods, and limn→∞xn are simply the required solutions. In most cases of interest, these sequences converge to their limits extremely slowly, or even diverge. One practical way to make the sequences {xn} converge more quickly is to apply to them vector extrapolation methods. In this work, we review two polynomial-type vector extrapolation methods that have proved to be very efficient convergence accelerators; namely, the minimal polynomial extrapolation (MPE) and the reduced rank extrapolation (RRE). We discuss their derivation, describe the most accurate and stable algorithms for their implementation along with the effective modes of usage, and present their convergence and stability theory. We also discuss their close connection with the method of Arnoldi and GMRES, two well known Krylov subspace methods for linear systems. Finally, we discuss some of their applications to different large-scale problems, such as solution of large-scale systems of equations, eigenvalue problems, computation of the PageRank of the Google matrix, and summation of vector-valued power series.

► Review of MPE and RRE, two extrapolation (convergence acceleration) methods for vector sequences. ► Short derivations, stable algorithms, and error analyses for MPE and RRE. ► Efficient ways of applying MPE and RRE to iterative solution of large sparse systems. ► Applications to computation of dominant eigenvectors of large sparse matrices. ► Applications to Google PageRank computation and to summation of vector-valued power series.