Technical Report CS-2018-02

Title: A Convergence Study for Reduced Rank Extrapolation on Nonlinear Systems
Authors: Avram Sidi
PDFCurrently accessibly only within the Technion network
Abstract: Reduced Rank Extrapolation (RRE) is a polynomial type method used to accelerate the convergence of sequences of vectors $\{x_m\}$. It is applied successfully in different disciplines of science and engineering in the solution of large and sparse systems of linear and nonlinear equations of very large dimension.

If $s$ is the solution to the system of equations $x=f(x)$, first, a vector sequence $\{x_m\}$ is generated via the fixed-point iterative scheme $x_{m+1}=f(\xx_m)$, $m=0,1,\ldots,$ and next, RRE is applied to this sequence to accelerate its convergence. RRE producesapproximations $s_{n,k}$ to $s$ that are of the form $s_{n,k}=\sum^k_{i=0}\gamma_i x_{n+i}$ for some scalars $\gamma_i$ depending (nonlinearly) on $x_n, x_{n+1},\ldots, x_{n+k+1}$ and satisfying $\sum^k_{i=0}\gamma_i=1$.

The convergence properties of RRE when applied in conjunction with linear $f(x)$ have been analyzed in different publications. In this work, we discuss the convergence of the $s_{n,k}$ obtained from RRE with nonlinear $f(x)$ (i)\,when $n\to\infty$ with fixed $k$, and (ii)\,in two so-called {\em cycling} modes.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2018
To the main CS technical reports page

Computer science department, Technion