On the Asymptotic Linear Convergence Speed of Anderson Acceleration, Nesterov Acceleration, and Nonlinear GMRES

DOI10.1137/20M1347139zbMath1490.65120arXiv2007.01996MaRDI QIDQ5161734

Yunhui He, Hans De Sterck

Publication date: 1 November 2021

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

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

zbMATH Keywords

alternating least squaresasymptotic convergenceAnderson accelerationcanonical tensor decompositionnonlinear GMRESNesterov acceleration

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Numerical computation of solutions to systems of equations (65H10) Numerical methods based on nonlinear programming (49M37) Iterative numerical methods for linear systems (65F10) Multilinear algebra, tensor calculus (15A69) Preconditioners for iterative methods (65F08)

Related Items (9)

Linear Asymptotic Convergence of Anderson Acceleration: Fixed-Point Analysis ⋮ On an improved PDE-based elliptic parameterization method for isogeometric analysis using preconditioned Anderson acceleration ⋮ Composite Anderson acceleration method with two window sizes and optimized damping ⋮ The effect of Anderson acceleration on superlinear and sublinear convergence ⋮ Direct nonlinear acceleration ⋮ Asymptotic convergence analysis and influence of initial guesses on composite Anderson acceleration ⋮ Anderson acceleration as a Krylov method with application to convergence analysis ⋮ Non-stationary Anderson acceleration with optimized damping ⋮ Anderson acceleration of gradient methods with energy for optimization problems

Uses Software

• TensorToolbox
• Poblano
• Chebfun
• Eigtool
• Anderson

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tensor Decompositions and Applications
• On acceleration methods for coupled nonlinear elliptic systems
• Linear and nonlinear programming.
• k-step iterative methods for solving nonlinear systems of equations
• The analysis of k-step iterative methods for linear systems from summability theory
• Domains containing the field of values of a matrix
• Krylov subspace acceleration for nonlinear multigrid schemes
• Introductory lectures on convex optimization. A basic course.
• Adaptive restart for accelerated gradient schemes
• Nonlinearly Preconditioned Optimization on Grassmann Manifolds for Computing Approximate Tucker Tensor Decompositions
• Composing Scalable Nonlinear Algebraic Solvers
• A Nonlinear GMRES Optimization Algorithm for Canonical Tensor Decomposition
• Local Convergence of the Alternating Least Squares Algorithm for Canonical Tensor Approximation
• Steepest descent preconditioning for nonlinear GMRES optimization
• Two classes of multisecant methods for nonlinear acceleration
• Anderson Acceleration for Fixed-Point Iterations
• Nonlinearly preconditioned L-BFGS as an acceleration mechanism for alternating least squares with application to tensor decomposition
• Accelerating Nonnegative Matrix Factorization Algorithms Using Extrapolation
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• A nonlinearly preconditioned conjugate gradient algorithm for rank‐R canonical tensor approximation
• Line search algorithms with guaranteed sufficient decrease
• Krylov Subspace Acceleration of Nonlinear Multigrid with Application to Recirculating Flows
• Any Nonincreasing Convergence Curve is Possible for GMRES
• An Adaptive Algebraic Multigrid Algorithm for Low-Rank Canonical Tensor Decomposition
• Iterative Solution of Nonlinear Equations in Several Variables
• Nesterov acceleration of alternating least squares for canonical tensor decomposition: Momentum step size selection and restart mechanisms
• A Proof That Anderson Acceleration Improves the Convergence Rate in Linearly Converging Fixed-Point Methods (But Not in Those Converging Quadratically)
• Convergence Analysis for Anderson Acceleration
• Some Remarks on the Elman Estimate for GMRES
• Iterative Procedures for Nonlinear Integral Equations

This page was built for publication: On the Asymptotic Linear Convergence Speed of Anderson Acceleration, Nesterov Acceleration, and Nonlinear GMRES