Extrapolation Methods for Vector Sequences 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 {x_n}, where the x_n are complex N-vectors 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 their limits are simply the required solutions of these systems. In most cases of interest, however, these sequences converge to their limits extremely slowly. One practical way to make these sequences converge more quickly is to apply to them vector extrapolation methods. In this lecture, 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 computer 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 consider some applications of MPE and RRE, such as solution of systems of nonlinear equations, summation of vector-valued power series, and computation of the PageRank of the Google Web matrix.

Speaker Bio: Avram Sidi received his Ph.D. from Tel Aviv University in 1978, and has been at the Computer Science Department of the Technion–Israel Institute of Technology, Haifa, Israel since 1977. Presently, he is a full professor and holds the Technion Administration Chair in Computer Science. He also worked for many years as a visiting scientist at NASA–Glenn Research Center, Cleveland, Ohio. One of his main areas of research is that of acceleration of convergence and extrapolation methods for scalar and vector sequences; he has been involved in the development, analysis, and algorithmic aspects, of extrapolation methods, old and new, and in their applications to computation of infinite-range integrals and the summation of infinite series of different kinds. His other areas of research are numerical integration, numerical solution of integral equations, Pad´e and related scalar- and vector-valued rational approximation procedures in the complex plane, numerical linear algebra, and asymptotic methods for different problems of numerical analysis. He is the author of the 2003 book ”Practical Extrapolation Methods: Theory and Applications” that covers the area of scalar extrapolation methods. He has authored and co-authored over a hundred journal papers in numerical analysis and approximation theory.

Note: Visitors from outside NIST must contact Robin Bickel; (301) 975-3668; at least 24 hours in advance.