Non-stationary Anderson acceleration with optimized damping

Abstract

Anderson acceleration (AA) has a long history of use and a strong recent interest due to its potential ability to dramatically improve the linear convergence of the fixed-point iteration. Most authors are simply using and analyzing the stationary version of Anderson acceleration (sAA) with a constant damping factor or without damping. Little attention has been paid to nonstationary algorithms. However, damping can be useful and is sometimes crucial for simulations in which the underlying fixed-point operator is not globally contractive. The role of this damping factor has not been fully understood. In the present work, we consider the non-stationary Anderson acceleration algorithm with optimized damping (AAoptD) in each iteration to further speed up linear and nonlinear iterations by applying one extra inexpensive optimization. We analyze the convergence rate this procedure and develop an efficient and inexpensive implementation scheme. We show by extensive numerical experiments that the proposed non-stationary Anderson acceleration with optimized damping procedure often converges much faster than stationary AA with constant damping, adaptive damping or without damping, especially in the cases larger window sizes are needed. We also observe that simple strategies like using constant damping factors and adaptive damping factors, sometimes, work very well for some problems while sometimes they are even worse than AA without damping. Our proposed method is usually more robust than AA with constant damping and adaptive damping. Moreover, we also observed from our numerical results that damping can be good, but choosing the wrong damping factors may slow down the convergence rate. Theoretical analysis of the effects of damping factors are needed and important.