Abstract supertype for acceleration objects that can be used to speed up a fixed-point iterations g = g(x) of a nonexpansive operator g. They must implement the following methods to communicate with the fixed-point algorithm:

  • update!(aa::AbstractAccelerator, g, x, num_iter) #stores the fixed-point iterates
  • accelerate!(g::AbstractVector, x, aa::AbstractAccelerator, num_iter) #recombines past iterates to determine an accelerated point and overwrites g
  • restart!(aa::AbstractAccelerator, args...; kwargs...) # algorithm tells the accelerator to restart

The algorithm has to be able to query the following information:

  • was_successful(aa::AbstractAccelerator) –> Bool #indicate whether accelerate! was succesful at the last iteration

The following method is optional:

  • log!(aa::AbstractAccelerator, args...; kwargs...) # algorithm tells accelerator to log certain information for debugging
AndersonAccelerator{T, BT, MT, RE} <: AbstractAccelerator

Accelerator object implementing Anderson Acceleration. Parameterized by:

  • T: AbstractFloat, floating-point type
  • BT: Broyden-type, i.e. Type1 or Type2
  • MT: AbstractMemory, how full memory buffers are handled
  • RE: AbstractRegularizer

Recombine past iterates to compute an accelerated point. Overwrite g with accelerated point. Uses QR-decomposition.


Depending on the AndersonAccelerator parameter AbstractMemory, dispatch on the correct method that handles the case when the memory buffers are full.


Choose regularisation parameter based on the frobenius norms of the matrices X, F (Fu, Zhang, Boyd, 2019).


update!(aa, g, x, iter)

  • Update history of accelerator aa with iterates g = g(xi)
  • Computes residuals f = x - g
  • The iteration iter is passed in for logging