topoptlab.accelerators module

topoptlab.accelerators.anderson(x: ndarray, xhist: List, max_history: int, damp: float = 0.9, **kwargs: Any) → ndarray[source]

Anderson acceleration to achieve convergence acceleration. It assumes that the numerical process resembles a fixed point iteration

x_[i+1] = f(x_[i])

that we seek to accelerate to achieve the solution

f(x)-x = 0.

We assume that we have the current iterate x_[i+1] available and a history of q+1 iterates as well. We define the incremental matrix

dX = [x_[k-m+1] - x_[k-m], … , x_[k] - x_[k-1]],

the residual

r_[i] = x_[i+1] - x[i]

and the incremental residual matrix

dR = [r_[k-m] … r_[k]]

To accelerate we find the gamma that minimizes

||dR@gamma - r_[k]||_[2]

and find the updated x_[k+1]

x_[k+1] = x_[k+1] - (dX + damp*dRx)@gamma

where damp is a damping parameter between zero and one.

For details check the wikipedia article or

Pratapa, Phanisri P., Phanish Suryanarayana, and John E. Pask. “Anderson acceleration of the Jacobi iterative method: An efficient alternative to Krylov methods for large, sparse linear systems.” Journal of Computational Physics 306 (2016): 43-54.

Parameters:

  • x (np.ndarray (n)) – current iterate

  • xhist (list) – history of iterations. The last element of the list

  • max_history (int) – maximum number of past results used for the current update.

  • damp (float) – damping applied to Anderson update.

Returns:

x – updated iterate.

Return type:

np.ndarray

topoptlab.accelerators.diis(x: ndarray, xhist: List, max_history: int, r: None | ndarray = None, rhist: None | List = None, damp: float = 0.9) → ndarray[source]

Direct inversion in the iterative subspace (DIIS) or also known as Pulay mixing for convergence acceleration. Two use cases have to be distinguished: i) a residual is available (e. g. we try to solve a linear system iteratively r = b - A@x) ii) no residual is available meaning we perform a recursion (e. g. optimization or a fixed point iteration).

Parameters:

  • x (np.ndarray (n)) – current iterate

  • xhist (list) – history of iterations. The current iterate is not in this list.

  • max_history (int) – maximum number of past results used for the current update.

  • r (np.ndarray (n)) – current residual (e. g. from a linear system ala r=b-A<qx)

  • rhist (list) – history of residuals.

  • damp (float) – damping applied to DIIS update.

Returns:

x – updated iterate.

Return type:

np.ndarray