Anderson Acceleration

class pathsim.optim.anderson.Anderson(m=4, restart=False)[source]

Bases: object

Anderson acceleration for fixed-point iteration.

Solves nonlinear equations in fixed-point form \(x = g(x)\) by computing the next iterate as a linear combination of previous iterates whose coefficients minimise the least-squares residual.

\[x_{k+1} = \sum_{i=0}^{m_k} \alpha_i^{(k)}\, g(x_{k-m_k+i}) \quad\text{with}\quad \alpha^{(k)} = \arg\min \bigl\|\sum_i \alpha_i\, r_{k-m_k+i}\bigr\|\]

where \(r_k = g(x_k) - x_k\) and \(m_k \le m\) is the current buffer depth.

In PathSim this class is the inner fixed-point solver used by the simulation engine to resolve algebraic loops (cycles in the block diagram). Each loop-closing ConnectionBooster owns an Anderson instance that accelerates convergence of the fixed-point iteration over the loop. The buffer depth m controls how many previous iterates are retained; larger values improve convergence on difficult loops at the cost of a small least-squares solve per iteration.

Parameters:

  • m (int) – buffer depth (number of stored iterates)

  • restart (bool) – if True, clear the buffer once it reaches depth m

References

solve(func, x0, iterations_max=100, tolerance=1e-06)[source]

Solve the function ‘func’ with initial value ‘x0’ up to a certain tolerance.

Note

This method is for testing purposes only and not used in the simulation loop.

Parameters:

  • func (callable) – function to solve

  • x0 (numeric) – starting value for solution

  • iterations_max (int) – maximum number of solver iterations

  • tolerance (float) – convergence condition

Returns:

  • x (numeric) – solution

  • res (float) – residual

  • i (int) – iteration count

reset()[source]

reset the anderson accelerator

step(x, g)[source]

Perform one iteration on the fixed-point solution.

Parameters:

  • x (float, array) – current solution

  • g (float, array) – current evaluation of g(x)

Returns:

  • x (float, array) – new solution

  • res (float) – residual norm, fixed point error

class pathsim.optim.anderson.NewtonAnderson(m=4, restart=False)[source]

Bases: Anderson

Hybrid Newton–Anderson fixed-point solver.

Extends Anderson by prepending a Newton step when a Jacobian of \(g\) is available. The Newton step

\[\tilde{x} = x - (J_g - I)^{-1}\,(g(x) - x)\]

provides a quadratically convergent initial correction; the subsequent Anderson mixing step then stabilises the iteration and damps oscillations.

In PathSim this solver is used inside every implicit ODE integration engine (BDF, DIRK, ESDIRK). When a block provides a local Jacobian (e.g. ODE or LTI blocks), the Newton pre-step yields much faster convergence of the implicit update equation, reducing the number of fixed-point iterations per timestep. Without a Jacobian the solver falls back to pure Anderson acceleration.

References

solve(func, x0, jac=None, iterations_max=100, tolerance=1e-06)[source]

Solve the function ‘func’ with initial value ‘x0’ up to a certain tolerance.

Parameters:

  • func (callable) – function to solve

  • x0 (numeric) – starting value for solution

  • jac (callable) – jacobian of ‘func’

  • iterations_max (int) – maximum number of solver iterations

  • tolerance (float) – convergence condition

Note

This method is for testing purposes only and not used in the simulation loop.

Returns:

  • x (numeric) – solution

  • res (float) – residual

  • i (int) – iteration count

step(x, g, jac=None)[source]

Perform one iteration on the fixed-point solution.

If the jacobian of g ‘jac’ is provided, a newton step is performed previous to anderson acceleration.

Parameters:

  • x (float, array) – current solution

  • g (float, array) – current evaluation of g(x)

  • jac (array) – evaluation of jacobian of ‘g’

Returns:

  • x (float, array) – new solution

  • res (float) – residual norm