This section describes the SUNNonlinSol implementation of a fixed point
(functional) iteration with optional Anderson acceleration. To access the
SUNNonlinSol_FixedPoint module, include the header file
sunnonlinsol/sunnonlinsol_fixedpoint.h
. We note that the
SUNNonlinSol_FixedPoint module is accessible from SUNDIALS integrators
without separately linking to the
libsundials_sunnonlinsolfixedpoint
module library.
To find the solution to
given an initial guess \(y^{(0)}\), the fixed point iteration computes a series of approximate solutions
where \(n\) is the iteration index. The convergence of this iteration may be accelerated using Anderson’s method [A1965], [WN2011], [FS2009], [LWWY2012]. With Anderson acceleration using subspace size \(m\), the series of approximate solutions can be formulated as the linear combination
where \(m_n = \min{\{m,n\}}\) and the factors
solve the minimization problem \(\min_\alpha \| F_n \alpha^T \|_2\) under the constraint that \(\sum_{i=0}^{m_n} \alpha_i = 1\) where
with \(f_i = G(y^{(i)}) - y^{(i)}\). Due to this constraint, in the limit of \(m=0\) the accelerated fixed point iteration formula (3) simplifies to the standard fixed point iteration (2).
Following the recommendations made in [WN2011], the SUNNonlinSol_FixedPoint implementation computes the series of approximate solutions as
with \(\Delta g_i = G(y^{(i+1)}) - G(y^{(i)})\) and where the factors
solve the unconstrained minimization problem \(\min_\gamma \| f_n - \Delta F_n \gamma^T \|_2\) where
with \(\Delta f_i = f_{i+1} - f_i\). The least-squares problem is solved by applying a QR factorization to \(\Delta F_n = Q_n R_n\) and solving \(R_n \gamma = Q_n^T f_n\).
The acceleration subspace size \(m\) is required when constructing
the SUNNonlinSol_FixedPoint object. The default maximum number of
iterations and the stopping criteria for the fixed point iteration are
supplied by the SUNDIALS integrator when SUNNonlinSol_FixedPoint
is attached to it. Both the maximum number of iterations and the
convergence test function may be modified by the user by calling
SUNNonlinSolSetMaxIters()
and
SUNNonlinSolSetConvTestFn()
functions after attaching the
SUNNonlinSol_FixedPoint object to the integrator.
The SUNNonlinSol_FixedPoint module provides the following constructor
for creating the SUNNonlinearSolver
object.
SUNNonlinSol_FixedPoint
(N_Vector y, int m)¶The function SUNNonlinSol_FixedPoint()
creates a
SUNNonlinearSolver
object for use with SUNDIALS integrators to
solve nonlinear systems of the form \(G(y) = y\).
Return value: a SUNNonlinSol object if the constructor exits
successfully, otherwise it will be NULL
.
Since the accelerated fixed point iteration
(2) does not require the setup or solution
of any linear systems, the SUNNonlinSol_FixedPoint module implements
all of the functions defined in sections SUNNonlinearSolver core functions
through SUNNonlinearSolver get functions except for the
SUNNonlinSolSetup()
, SUNNonlinSolSetLSetupFn()
,
and SUNNonlinSolSetLSolveFn()
functions, that are set to
NULL
. The SUNNonlinSol_FixedPoint functions have the same names as
those defined by the generic SUNNonlinSol API with _FixedPoint
appended to the function name. Unless using the
SUNNonlinSol_FixedPoint module as a standalone nonlinear solver the
generic functions defined in sections SUNNonlinearSolver core functions
through SUNNonlinearSolver get functions should be called in favor of the
SUNNonlinSol_FixedPoint-specific implementations.
The SUNNonlinSol_FixedPoint module also defines the following additional user-callable functions.
SUNNonlinSolGetSysFn_FixedPoint
(SUNNonlinearSolver NLS, SUNNonlinSolSysFn *SysFn)¶The function SUNNonlinSolGetSysFn_FixedPoint()
returns
the fixed-point function that defines the nonlinear system.
Return value: The return value is zero for a successful call, and a negative value for a failure.
Notes: This function is intended for users that wish to evaluate the fixed-point function in a custom convergence test function for the SUNNonlinSol_FixedPoint module. We note that SUNNonlinSol_FixedPoint will not leverage the results from any user calls to SysFn.
SUNNonlinSolSetDamping_FixedPoint
(SUNNonlinearSolver NLS, realtype beta)¶The function SUNNonlinSolSetDamping_FixedPoint()
sets the damping
parameter \(\beta\) to use with Anderson acceleration. By default damping
is disabled i.e., \(\beta = 1.0\).
Return value: The return value is zero for a successful call,
SUN_NLS_MEM_NULL
if NLS
is NULL
, or SUN_NLS_ILL_INPUT
if
beta
is negative.
Notes: A beta
value should be great than zero and less than one if
damping is to be used. A value of one or more will disable damping.
SUNNonlinSolSetInfoFile_FixedPoint
(SUNNonlinearSolver NLS, FILE* info_file)¶The function SUNNonlinSolSetInfoFile_FixedPoint()
sets the
output file where all informative (non-error) messages should be directed.
stdout
by default);NULL
input will disable outputNULL
Notes:
This function is intended for users that wish to monitor the nonlinear
solver progress. By default, the file pointer is set to stdout
.
SUNDIALS must be built with the CMake option ``SUNDIALS_BUILD_WITH_MONITORING``, to utilize this function. See section Configuration options (Unix/Linux) for more information.
SUNNonlinSolSetPrintLevel_FixedPoint
(SUNNonlinearSolver NLS, int print_level)¶The function SUNNonlinSolSetPrintLevel_FixedPoint()
specifies
the level of verbosity of the output.
NLS – a SUNNonlinSol object
print_level – flag indicating level of verbosity; must be one of:
- 0, no information is printed (default)
- 1, for each nonlinear iteration the residual norm is printed
NULL
Notes: This function is intended for users that wish to monitor the nonlinear solver progress. By default, the print level is 0.
SUNDIALS must be built with the CMake option ``SUNDIALS_BUILD_WITH_MONITORING``, to utilize this function. See section Configuration options (Unix/Linux) for more information.
The content field of the SUNNonlinSol_FixedPoint module is the following structure.
struct _SUNNonlinearSolverContent_FixedPoint {
SUNNonlinSolSysFn Sys;
SUNNonlinSolConvTestFn CTest;
int m;
int *imap;
realtype *R;
booleantype damping
realtype beta
realtype *gamma;
realtype *cvals;
N_Vector *df;
N_Vector *dg;
N_Vector *q;
N_Vector *Xvecs;
N_Vector yprev;
N_Vector gy;
N_Vector fold;
N_Vector gold;
N_Vector delta;
int curiter;
int maxiters;
long int niters;
long int nconvfails;
void *ctest_data;
int print_level;
FILE* info_file;
};
The following entries of the content field are always allocated:
Sys
– function for evaluating the nonlinear system,CTest
– function for checking convergence of the fixed point iteration,yprev
– N_Vector
used to store previous fixed-point iterate,gy
– N_Vector
used to store \(G(y)\) in fixed-point algorithm,delta
– N_Vector
used to store difference between successive fixed-point iterates,curiter
– the current number of iterations in the solve attempt,maxiters
– the maximum number of fixed-point iterations allowed in
a solve,niters
– the total number of nonlinear iterations across all
solves,nconvfails
– the total number of nonlinear convergence failures across all solves,ctest_data
– the data pointer passed to the convergence test function, andm
– number of acceleration vectors.print_level
- controls the amount of information to be printed to the info fileinfo_file
- the file where all informative (non-error) messages will be directedIf Anderson acceleration is requested (i.e., \(m>0\) in the call
to SUNNonlinSol_FixedPoint()
), then the following items are also
allocated within the content field:
imap
– index array used in acceleration algorithm (length m
),damping
– a flag indicating if damping is enabled,beta
– the damping parameter,R
– small matrix used in acceleration algorithm (length m*m
),gamma
– small vector used in acceleration algorithm (length m
),cvals
– small vector used in acceleration algorithm (length m+1
),df
– array of N_Vectors
used in acceleration algorithm (length m
),dg
– array of N_Vectors
used in acceleration algorithm (length m
),q
– array of N_Vectors
used in acceleration algorithm (length m
),Xvecs
– N_Vector
pointer array used in acceleration algorithm (length m+1
),fold
– N_Vector
used in acceleration algorithm, andgold
– N_Vector
used in acceleration algorithm.For SUNDIALS integrators that include a Fortran interface, the
SUNNonlinSol_FixedPoint module also includes a Fortran-callable
function for creating a SUNNonlinearSolver
object.
FSUNFixedPointInit
(CODE, M, IER)¶The function FSUNFixedPointInit()
can be called for
Fortran programs to create a SUNNonlinearSolver
object for use
with SUNDIALS integrators to solve nonlinear systems of the form
\(G(y) = y\).
This routine must be called after the N_Vector
object has
been initialized.
int
, input) – flag denoting the SUNDIALS solver
this matrix will be used for: CVODE=1, IDA=2, ARKode=4.int
, input) – the number of acceleration vectors.int
, output) – return flag (0 success, -1 for
failure). See printed message for details in case
of failure.