Asymptotic convergence analysis and influence of initial guesses on composite Anderson acceleration

Asymptotic convergence analysis and influence of initial guesses on composite Anderson acceleration

Chen, Kewang (Nanjing University of Information Sciences and Technology)
Vuik, Cornelis (TU Delft Delft Institute of Applied Mathematics)

2023

Although Anderson acceleration AA(m) has been widely used to speed up nonlinear solvers, most authors are simply using and studying the stationary version of Anderson acceleration. The behavior and full potential of the non-stationary version of Anderson acceleration methods remain an open question. Motivated by the hybrid linear solver GMRESR (GMRES Recursive), we recently proposed a set of non-stationary Anderson acceleration algorithms with dynamic window sizes AA(m,AA(n)) for solving both linear and nonlinear problems. Significant gains are observed for our proposed algorithms but these gains are not well understood. In the present work, we first consider the case of using AA(m,AA(1)) for accelerating linear fixed-point iteration and derive the polynomial residual update formulas for non-stationary AA(m,AA(1)). Like stationary AA(m), we find that AA(m,AA(1)) with general initial guesses is also a multi-Krylov method and possesses a memory effect. However, AA(m,AA(1)) has higher order degree of polynomials and a stronger memory effect than that of AA(m) at the k-th iteration, which might explain the better performance of AA(m,AA(1)) compared to AA(m) as observed in our numerical experiments. Moreover, we further study the influence of initial guess on the asymptotic convergence factor of AA(1, AA(1)). We show a scaling invariance property of the initial guess x for the AA(1,AA(1)) method in the linear case. Then, we study the root-linear asymptotic convergence factor under scaling of the initial guess and we explicitly indicate the dependence of root-linear asymptotic convergence factors on the initial guess. Lastly, we numerically examine the influence of the initial guess on the asymptotic convergence factor of AA(m) and AA(m,AA(n)) for both linear and nonlinear problems.

Dynamic window sizes
Fixed-point iteration
Krylov method
Non-stationary Anderson acceleration

http://resolver.tudelft.nl/uuid:9032068f-9b0d-46cd-870c-d570dfd42098

https://doi.org/10.1007/s10444-023-10095-3

2024-06-13

1019-7168

Advances in Computational Mathematics, 49 (6)

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

journal article

© 2023 Kewang Chen, Cornelis Vuik