A convergence study for reduced rank extrapolation on nonlinear systems

DOI10.1007/S11075-019-00788-6MaRDI QIDQ2189405zbMATH OpenOpenAlexFDO

Authors Avram Sidi

Publication date 15 June 2020

Published in Numerical Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.03199

zbMATH Keywords

Krylov subspace methodsnonlinear equationsminimal polynomial extrapolationvector extrapolation methodsreduced rank extrapolationcycling mode

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Extrapolation to the limit, deferred corrections (65B05) Numerical solution of nonlinear eigenvalue and eigenvector problems (65H17)

Abstract: Reduced Rank Extrapolation (RRE) is a polynomial type method used to accelerate the convergence of sequences of vectors $$. 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 $$ is the solution to the system of equations $$, first, a vector sequence $$ is generated via the fixed-point iterative scheme $$, $m=0,1,ldots,$ and next, RRE is applied to this sequence to accelerate its convergence. RRE produces approximations $$ to $$ that are of the form $$ for some scalars $gamm{a}_i$ depending (nonlinearly) on $$ and satisfying $su{m}_{i=0}^{k}gamm{a}_i=1$. The convergence properties of RRE when applied in conjunction with linear $$ have been analyzed in different publications. In this work, we discuss the convergence of the $$ obtained from RRE with nonlinear $$ (i),when $noinfty$ with fixed $k$, and (ii),in two so-called {em cycling} modes.

Recommendations

• Convergence and Stability Properties of Minimal Polynomial and Reduced Rank Extrapolation Algorithms
• Nonlinear Schwarz iterations with reduced rank extrapolation
• Convergence theory of extrapolated iterative methods for a certain class of non-symmetric linear systems
• Model Reduction for a Class of Convergent Nonlinear Systems
• Componentwise fast convergence in the solution of full-rank systems of nonlinear equations
• A globally convergent inexact-Newton method for solving reducible nonlinear systems of equations
• Approximate norm descent methods for constrained nonlinear systems
• On the semiconvergence of extrapolated iterative methods for singular linear systems
• On the optimization of extrapolation methods for singular linear systems
• Convergence of extrapolated method for solving non-Hermitian linear systems

Cites work

• scientific article; zbMATH DE number 3114505 (Why is no real title available?)
• scientific article; zbMATH DE number 52076 (Why is no real title available?)
• scientific article; zbMATH DE number 845762 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 1433445 (Why is no real title available?)
• scientific article; zbMATH DE number 3362908 (Why is no real title available?)
• scientific article; zbMATH DE number 3362909 (Why is no real title available?)
• scientific article; zbMATH DE number 3381785 (Why is no real title available?)
• A Polynomial Extrapolation Method for Finding Limits and Antilimits of Vector Sequences
• Acceleration Techniques for Iterated Vector and Matrix Problems
• Acceleration of Convergence of Vector Sequences
• Acceleration of the convergence of iterative processes and a method of solving systems of non-linear equations
• Accélération de la convergence en analyse numérique
• Analysis of some vector extrapolation methods for solving systems of linear equations
• Anderson acceleration for fixed-point iterations
• Computation of the periodic steady-state response of nonlinear networks by extrapolation methods
• Convergence acceleration for the iterative solution of the equations X = AX + f
• Convergence analysis for Anderson acceleration
• Convergence and Stability Properties of Minimal Polynomial and Reduced Rank Extrapolation Algorithms
• Convergence and stability analyses for some vector extrapolation methods in the presence of defective iteration matrices
• Convergence of intermediate rows of minimal polynomial and reduced rank extrapolation tables
• Efficient implementation of minimal polynomial and reduced rank extrapolation methods
• Extension and completion of Wynn's theory on convergence of columns of the epsilon table
• Extrapolation Methods for Vector Sequences
• Extrapolation methods theory and practice
• Extrapolation vs. projection methods for linear systems of equations
• Generalized inverses. Theory and applications.
• Généralisations de la transformation de Shanks, de la table de Padé et de l'\(\varepsilon\)-algorithme
• Iterative Procedures for Nonlinear Integral Equations
• LU implementation of the modified minimal polynomial extrapolation method for solving linear and nonlinear systems
• Least-square acceleration of iterative methods for linear equations
• Minimal polynomial and reduced rank extrapolation methods are related
• On Error Bounds for Generalized Inverses
• On a Device for Computing the e m (S n ) Transformation
• On the Continuity of the Generalized Inverse
• On the Convergence and Stability of the Epsilon Algorithm
• On the Solution of Systems of Equations by the Epsilon Algorithm of Wynn
• Perturbation theory for pseudo-inverses
• Row convergence theorems for generalised inverse vector-valued Padé approximants
• Some results about vector extrapolation methods and related fixed-point iterations
• The quadratic convergence of the topological epsilon algorithm for systems of nonlinear equations
• Upper bounds for convergence rates of acceleration methods with initial iterations
• Vector extrapolation methods with applications

Cited in

(3)

• Data-enabled reduction of the time complexity of iterative solvers
• A survey of Shanks' extrapolation methods and their applications
• Nonlinear Schwarz iterations with reduced rank extrapolation

Describes a project that uses

Uses Software

• Anderson

This page was built for publication: A convergence study for reduced rank extrapolation on nonlinear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2189405)