Composite Anderson acceleration method with two window sizes and optimized damping

Abstract

In this article, we propose and analyze a set of fully nonstationary Anderson acceleration (AA) algorithms with two window sizes and optimized damping. Although AA has been used for decades to speed up nonlinear solvers in many applications, most authors are simply using and analyzing the stationary version of AA (sAA) with fixed window size and a constant damping factor. The behavior and potential of the nonstationary version of AA methods remain an open question. Most efficient linear solvers however use composable algorithmic components. Similar ideas can be used for AA to solve nonlinear systems. Thus in the present work, to develop nonstationary AA algorithms, we first propose a systematic way to dynamically alternate the window size (Formula presented.) by the multiplicative composite combination, which means we apply sAA((Formula presented.)) in the outer loop and apply sAA((Formula presented.)) in the inner loop. By doing this, significant gains can be achieved. Second, to make AA to be a fully nonstationary algorithm, we need to combine these strategies with our recent work on the nonstationary AA algorithm with optimized damping (AAoptD), which is another important direction of producing nonstationary AA and nice performance gains have been observed. Moreover, we also investigate the rate of convergence of these nonstationary AA methods under suitable assumptions. Finally, our numerical results show that some of these proposed nonstationary AA algorithms converge faster than the stationary sAA method and they may significantly reduce the storage and time to find the solution in many cases.