dg::AndersonAcceleration< ContainerType > Struct Template Reference

Anderson Acceleration of Fixed Point/Richardson Iteration for the nonlinear equation \( f(x) = b\). More...

Public Types
using	value_type = get_value_type< ContainerType >
	the value type of the time variable (float or double) More...
using	container_type = ContainerType

Public Member Functions
	AndersonAcceleration ()=default
	Allocate nothing, Call construct method before usage. More...
	AndersonAcceleration (const ContainerType &copyable)
	Allocate memory for Fixed point iteration. More...
	AndersonAcceleration (const ContainerType &copyable, unsigned mMax)
	Allocate memory for the object. More...
template<class ... Params>
void	construct (Params &&...ps)
	Perfect forward parameters to one of the constructors. More...
const ContainerType &	copyable () const
	Return an object of same size as the object used for construction. More...
void	set_throw_on_fail (bool throw_on_fail)
	Set or unset a throw on failure-to-converge. More...
template<class MatrixType , class ContainerType0 , class ContainerType1 , class ContainerType2 >
unsigned	solve (MatrixType &&f, ContainerType0 &x, const ContainerType1 &b, const ContainerType2 &weights, value_type rtol, value_type atol, unsigned max_iter, value_type damping, unsigned restart, bool verbose)
	Solve the system \( f(x) = b \) in the given norm. More...

Detailed Description

template<class ContainerType>
struct dg::AndersonAcceleration< ContainerType >

Anderson Acceleration of Fixed Point/Richardson Iteration for the nonlinear equation \( f(x) = b\).

This class implements the Anderson acceleration of the fixed point iteration algorithm described by https://users.wpi.edu/~walker/Papers/Walker-Ni,SINUM,V49,1715-1735.pdf with implementation details in //https://users.wpi.edu/~walker/Papers/anderson_accn_algs_imps.pdf As recommended by https://arxiv.org/pdf/1803.06673.pdf we periodically restart the acceleration to improve convergence behaviour.

    // create volume on previously defined grid
    const dg::HVec w2d = dg::create::weights( grid);
 
    // Create normalized Laplacian
    dg::Elliptic<dg::CartesianGrid2d, dg::HMatrix, dg::HVec> A( grid);
 
    // allocate memory
    dg::AndersonAcceleration<dg::HVec > acc( copyable_vector, 10);
 
    // Evaluate right hand side and solution on the grid
    dg::HVec b = dg::evaluate ( laplace_fct, grid);
    const dg::HVec solution = dg::evaluate ( fct, grid);
 
    const double eps = 1e-6;
    std::cout << "Number of iterations "<< acc.solve( A, x, b, w2d, eps, eps, max_iter, damping, restart, true)<<std::endl;

Template Parameters

ContainerType

Any class for which a specialization of TensorTraits exists and which fulfills the requirements of the there defined data and execution policies derived from AnyVectorTag and AnyPolicyTag. Among others dg::HVec (serial), dg::DVec (cuda / omp), dg::MHVec (mpi + serial) or dg::MDVec (mpi + cuda / omp) std::vector<dg::DVec> (vector of shared device vectors), std::array<double, 4> (array of 4 doubles) or std::map < std::string, dg::DVec> ( a map of named vectors) double (scalar) and other primitive types ... If there are several ContainerTypes in the argument list, then TensorTraits must exist for all of them

See also

See The dg dispatch system for a detailed explanation of our type dispatch system

Member Typedef Documentation

container_type

template<class ContainerType >

using dg::AndersonAcceleration< ContainerType >::container_type = ContainerType

the type of the vector class in use

value_type

template<class ContainerType >

using dg::AndersonAcceleration< ContainerType >::value_type = get_value_type<ContainerType>

the value type of the time variable (float or double)

Constructor & Destructor Documentation

AndersonAcceleration() [1/3]

template<class ContainerType >

dg::AndersonAcceleration< ContainerType >::AndersonAcceleration ( )

default

Allocate nothing, Call construct method before usage.

AndersonAcceleration() [2/3]

template<class ContainerType >

dg::AndersonAcceleration< ContainerType >::AndersonAcceleration ( const ContainerType &  copyable )

inline

Allocate memory for Fixed point iteration.

This version sets mMax to zero reducing the solve method to Fixed Point (or Richardson if the damping parameter is != 1 in the solve() method) iteration

Parameters

copyable

A ContainerType must be copy-constructible from this

AndersonAcceleration() [3/3]

template<class ContainerType >

dg::AndersonAcceleration< ContainerType >::AndersonAcceleration ( const ContainerType &  copyable, unsigned  mMax  )

inline

Allocate memory for the object.

Parameters

copyable

A ContainerType must be copy-constructible from this

mMax

The maximum number of vectors to include in the optimization procedure. mMax+1 is the number of solutions involved in computing the new solution. Something between 3 and 10 are good values but higher values mean more storage space that needs to be reserved. If mMax==0 then the algorithm is equivalent to Fixed Point (or Richardson if the damping parameter is != 1 in the solve() method) iteration i.e. no optimization and only 1 solution needed to compute a new solution.

Member Function Documentation

construct()

template<class ContainerType >

template<class ... Params>

void dg::AndersonAcceleration< ContainerType >::construct ( Params &&...  ps )

inline

Perfect forward parameters to one of the constructors.

Template Parameters

Params

deduced by the compiler

Parameters

ps	parameters forwarded to constructors

copyable()

template<class ContainerType >

const ContainerType & dg::AndersonAcceleration< ContainerType >::copyable ( ) const

inline

Return an object of same size as the object used for construction.

Returns

A copyable object; what it contains is undefined, its size is important

set_throw_on_fail()

template<class ContainerType >

void dg::AndersonAcceleration< ContainerType >::set_throw_on_fail ( bool  throw_on_fail )

inline

Set or unset a throw on failure-to-converge.

Parameters

throw_on_fail

If true, the solve method will thow a dg::Fail if it is unable to converge

Note

the default value is true

solve()

template<class ContainerType >

template<class MatrixType , class ContainerType0 , class ContainerType1 , class ContainerType2 >

unsigned dg::AndersonAcceleration< ContainerType >::solve	(	MatrixType &&	f,
		ContainerType0 &	x,
		const ContainerType1 &	b,
		const ContainerType2 &	weights,
		value_type	rtol,
		value_type	atol,
		unsigned	max_iter,
		value_type	damping,
		unsigned	restart,
		bool	verbose
	)

Solve the system \( f(x) = b \) in the given norm.

Iterates until \( ||f(x)-b|| < a_{\mathrm{tol}} + r_{\mathrm{tol}} ||b||\)

Parameters

f	The function y=f(x) in the form f(x,y). The first argument is the input and the second the output.
x	Contains an initial guess on input and the solution on output.
b	The right hand side vector.
weights	The weights define the norm for the stopping condition of the solver and the scalar product in which the least square problem is computed
rtol	Relative error condition with respect to b
atol	Absolute error condition
max_iter	Maxmimum number of iterations
damping	Paramter to prevent too large jumps around the actual solution. Hard to determine in general but values between 1e-2 and 1e-4 are good values to begin with. This is the parameter that appears in Richardson iteration. It is beter to have it too small than too large (where it can lead to divergence of the solver)
restart	Number >= mMax that indicates after how many iterations to restart the acceleration. Periodic restarts are important for this method. Per default it should be the same value as mMax but mMax+1 or higher could be valuable to consider (but usually are worse than mMax). Lower values restart<mMax are equivalent to setting mMax=restart.
verbose	If true writes intermediate errors to std::cout

Returns

Number of iterations used to achieve desired precision

Note

The method will throw dg::Fail if the desired accuracy is not reached within max_iterations You can unset this behaviour with the set_throw_on_fail member

Template Parameters

MatrixType

Any class for which a specialization of TensorTraits exists and defines a tensor_category derived from AnyMatrixTag. Furthermore, any functor/lambda type with signature void operator()( const ContainerType0&, ContainerType1&) . For example scalar or Container: Scalars and containers act as diagonal matrices. std::function<void( const ContainerType0&, ContainerType1&)> dg::HMatrix and dg::IHMatrix with dg::HVec or std::vector<dg::HVec> dg::DMatrix and dg::IDMatrix with dg::DVec or std::vector<dg::DVec> dg::MHMatrix with dg::MHVec or std::vector<dg::MHVec> dg::MDMatrix with dg::MDVec or std::vector<dg::MDVec> In case of SelfMadeMatrixTag only those blas2 functions that have a corresponding member function in the Matrix class (e.g. symv( const ContainerType0&, ContainerType1&); ) can be called. If a Container has the RecursiveVectorTag, then the matrix is applied to each of the elements unless the type has the SelfMadeMatrixTag or is a Functor type.

ContainerType

Any class for which a specialization of TensorTraits exists and which fulfills the requirements of the there defined data and execution policies derived from AnyVectorTag and AnyPolicyTag. Among others dg::HVec (serial), dg::DVec (cuda / omp), dg::MHVec (mpi + serial) or dg::MDVec (mpi + cuda / omp) std::vector<dg::DVec> (vector of shared device vectors), std::array<double, 4> (array of 4 doubles) or std::map < std::string, dg::DVec> ( a map of named vectors) double (scalar) and other primitive types ... If there are several ContainerTypes in the argument list, then TensorTraits must exist for all of them

See also

See The dg dispatch system for a detailed explanation of our type dispatch system

---

The documentation for this struct was generated from the following file:

• andersonacc.h