Anderson acceleration with approximate calculations: applications to scientific computing

Authors Massimiliano Lupo Pasini, M. Paul Laiu

Publication date 8 June 2022

Iterative numerical methods for linear systems (65F10) Computational methods for sparse matrices (65F50) Interval and finite arithmetic (65G30) Roundoff error (65G50) Stability and convergence of numerical methods for boundary value problems involving PDEs (65N12) Error bounds for boundary value problems involving PDEs (65N15) Complexity and performance of numerical algorithms (65Y20) Applications to the sciences (65Z05) General topics in artificial intelligence (68T01) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Abstract: We provide rigorous theoretical bounds for Anderson acceleration (AA) that allow for efficient approximate residual calculations in AA, which in turn reduce computational time and memory storage while maintaining convergence. Specifically, we propose a reduced variant of AA, which consists in projecting the least-squares used to compute the Anderson mixing onto a subspace of reduced dimension. The dimensionality of this subspace adapts dynamically at each iteration as prescribed by computable heuristic quantities guided by rigorous theoretical error bounds. The use of heuristics to monitor the error introduced by approximate calculations, combined with the check on monotonicity of the convergence, ensures the convergence of the numerical scheme within a prescribed tolerance threshold on the residual. We numerically show and assess the performance of AA with approximate calculations on: (i) linear deterministic fixed-point iterations arising from the Richardson's scheme to solve linear systems with open-source benchmark matrices with various preconditioners and (ii) non-linear deterministic fixed-point iterations arising from non-linear time-dependent Boltzmann equations.

This page was built for publication: Anderson acceleration with approximate calculations: applications to scientific computing

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