# Module Kinsol

module Kinsol: sig .. end

Solves nonlinear systems using Newton-Krylov techniques.

This module solves numerically problems of the form $F(u) = 0$ given an initial guess $u_0$.

This documented interface is structured as follows.

Author(s): Timothy Bourke (Inria/ENS), Jun Inoue (Inria/ENS), Marc Pouzet (UPMC/ENS/Inria)
• Version: 6.1.0

type ('data, 'kind) session = ('data, 'kind) session

A session with the KINSOL solver.

An example session with Kinsol (kinsol_skel.ml):

open Sundials

(* 1. Define a system function. *)
let pi, e = 4. *. atan 1., exp 1.
let sysf u r =
r.{0} <- 0.5 *. sin(u.{0}*.u.{1}) -. 0.25 *. u.{1} /. pi -. 0.5 *. u.{0};
r.{1} <- (1. -. 0.25/.pi)*.(exp(2.*.u.{0})-.e) +. e*.u.{1}/.pi -. 2.*.e*.u.{0};
r.{2} <- u.{2} -. u.{0} +. 0.25;
r.{3} <- u.{3} -. u.{0} +. 1.0;
r.{4} <- u.{4} -. u.{1} +. 1.5;
r.{5} <- u.{5} -. u.{1} +. 2.0 *. pi

(* 2. Set vector with initial guess.
The length of this vector determines the problem size. *)
let ud = RealArray.of_list [ 0.25; 1.5; 0.; -0.75; 0.; 1.5 -. 2. *.pi ]
let u = Nvector_serial.wrap ud

(* 3. Create and initialize a solver session.
This will initialize a specific linear solver. *)
let m = Matrix.dense 6
let s = Kinsol.(init ~lsolver:(Dls.(solver (dense u m))) sysf u);;

(* 4. Set optional inputs, e.g.,
call [set_*] functions to change solver parameters. *)
let c = RealArray.of_list [
Constraint.unconstrained;
Constraint.unconstrained;
Constraint.geq_zero;
Constraint.leq_zero;
Constraint.geq_zero;
Constraint.leq_zero ] in
Kinsol.set_constraints s (Nvector_serial.wrap c);
Kinsol.set_func_norm_tol s 1.0e-5;
Kinsol.set_scaled_step_tol s 1.0e-5;
Kinsol.set_max_setup_calls s 1;;

(* 5. Solve the problem. *)
let snv = Nvector_serial.make (RealArray.length ud) 1.0 in
ignore (Kinsol.(solve s u Newton snv snv));

Printf.printf "%8.5g %8.6g\n" ud.{0} ud.{1};;

(* 6. Get optional outputs,
call the [get_*] functions to examine solver statistics. *)
let fnorm = Kinsol.get_func_norm s;;

type [> Nvector_serial.kind ] serial_session = (Nvector_serial.data, [> Nvector_serial.kind ] as 'a) session

Alias for sessions based on serial nvectors.

### Linear solvers

type ('data, 'kind) linear_solver = ('data, 'kind) linear_solver

Linear solvers used by Kinsol.

type [> Nvector_serial.kind ] serial_linear_solver = (Nvector_serial.data, [> Nvector_serial.kind ] as 'a) linear_solver

Alias for linear solvers that are restricted to serial nvectors.

type 'd double = 'd * 'd

Workspaces with two temporary vectors.

type ('t, 'd) jacobian_arg = ('t, 'd) jacobian_arg = {
    jac_u : 'd; (* The current unscaled iterate. *)    jac_fu : 'd; (* The current value of the vector $F(u)$. *)    jac_tmp : 't; (* Workspace data. *)
}

Arguments common to Jacobian callback functions.

type 'data sysfn = 'data -> 'data -> unit

System function that defines nonlinear problem. The call sysfun u fval must calculate $F(u)$ into fval using the current value vector u.

Raising Sundials.RecoverableFailure indicates a recoverable error. Any other exception is treated as an unrecoverable error.

u and fval should not be accessed after the function returns.

module Dls: sig .. end

Direct Linear Solvers operating on dense, banded, and sparse matrices.

module Spils: sig .. end

Scaled Preconditioned Iterative Linear Solvers.

val matrix_embedded_solver : (unit, 'data, 'kind, [> MatE ]) Sundials.LinearSolver.t ->       ('data, 'kind) linear_solver

Create a Kinsol-specific linear solver from a generic matrix embedded solver.

### Solver initialization and use

type orthaa = 
 | MGS (* Modified Gram Schmidt (default) (KIN_ORTH_MGS) *) | ICWY (* Inverse Compact WY Modified Gram Schmidt (KIN_ORTH_ICWY) *) | CGS2 (* Classical Gram Schmidt with Reorthogonalization (KIN_ORTH_CGS2) *) | DCGS2 (* Classical Gram Schmidt with Delayed Reorthogonlization (KIN_ORTH_DCGS2) *)

Orthogonalization routines of the QR factorization portion of Anderson acceleration.

val init : ?context:Sundials.Context.t ->       ?max_iters:int ->       ?maa:int ->       ?orthaa:orthaa ->       ?lsolver:('data, 'kind) linear_solver ->       'data sysfn ->       ('data, 'kind) Nvector.t -> ('data, 'kind) session

Creates and initializes a session with the Kinsol solver. The call init ~max_lin_iters:mli ~maa:maa ~linsolv:ls f tmpl has as arguments:

• mli, the maximum number of nonlinear iterations allowed,
• maa, the size of the Anderson acceleration subspace for the Picard and FixedPoint strategies,
• orthaa, specifies the othogonalization routine to be used in the QR factorization portion of Anderson acceleration,
• ls, the linear solver to use (required for the Newton, LineSearch, and Picard strategies),
• f, the system function of the nonlinear problem, and,
• tmpl a template to initialize the session (e.g., the initial guess vector).

By default, the session is created using the context returned by Sundials.Context.default, but this can be overridden by passing an optional context argument.

The orthaa argument is ignored in Sundials < 6.0.0.

type strategy = 
 | Newton (* Basic Newton iteration. (KIN_NONE) *) | LineSearch (* Newton iteration with globalization. (KIN_LINESEARCH) *) | Picard (* Picard iteration with Anderson Acceleration. (KIN_PICARD) *) | FixedPoint (* Fixed-point iteration with Anderson Acceleration. (KIN_FP) *)

Strategy used to solve the nonlinear system.

type result = 
 | Success (* The scaled norm of $F(u)$ is less than fnormtol. See Kinsol.set_func_norm_tol. (KIN_SUCCESS) *) | InitialGuessOK (* The initial guess already satisfies the system. (KIN_INITIAL_GUESS_OK) *) | StoppedOnStepTol (* Stopped based on scaled step length. The current iterate is an approximate solution, or the algorithm stalled near an invalid solution, or scsteptol is too large (see Kinsol.set_scaled_step_tol). (KIN_STEP_LT_STPTOL) *)

Results of nonlinear solution attempts.

val solve : ('d, 'k) session ->       ('d, 'k) Nvector.t ->       strategy -> ('d, 'k) Nvector.t -> ('d, 'k) Nvector.t -> result

Computes an approximate solution to a nonlinear system. The call solve s u strategy u_scale f_scale has arguments:

• s, a solver session,
• u, an initial guess that is replaced with an approximate solution for $F(u) = 0$,
• strategy, strategy used to solve the nonlinear system,
• u_scale, the diagonal elements of the scaling matrix $D_u$ for vector u chosen so that all $D_u u$ all have roughly the same magnitude when u is close to a root of $F(u)$, and,
• f_scale, the diagonal elements of the scaling matrix $D_f$ for $F(u)$ chosen so that all $D_f F(u)$ have roughtly the same magnitude when u is not near a root of $F(u)$.

The function either returns a Kinsol.result or raises one of the exceptions listed below.

Raises
• MissingLinearSolver A linear solver is required but was not given.
• IllInput Missing or illegal solver inputs.
• LineSearchNonConvergence Line search could not find a suitable iterate.
• MaxIterationsReached The maximum number of nonlinear iterations was reached.
• MaxNewtonStepExceeded Five consecutive steps satisfied a scaled step length test.
• LineSearchBetaConditionFailure Line search could not satisfy the beta-condition.
• LinearSolverNoRecovery The Kinsol.Spils.prec_solve_fn callback raised Sundials.RecoverableFailure but the preconditioner is already current.
• LinearSolverInitFailure Linear solver initialization failed.
• LinearSetupFailure Linear solver setup failed unrecoverably.
• LinearSolveFailure Linear solver solution failed unrecoverably.
• SystemFunctionFailure The Kinsol.sysfn callback failed unrecoverably.
• FirstSystemFunctionFailure The Kinsol.sysfn callback raised Sundials.RecoverableFailure when first called.
• RepeatedSystemFunctionFailure The Kinsol.sysfn callback raised Sundials.RecoverableFailure repeatedly.
• See Sundials: KINSol

### Modifying the solver (optional input functions)

val set_no_init_setup : ('d, 'k) session -> unit

Specifies that an initial call to the preconditioner setup function should not be made. This feature is useful when solving a sequence of problems where the final preconditioner values of one problem become the initial values for the next problem.

val set_init_setup : ('d, 'k) session -> unit

Specifies that an initial call to the preconditioner setup function should be made (the default).

val set_no_res_mon : [> Nvector_serial.kind ] serial_session -> unit

Disables the nonlinear residual monitoring scheme that controls Jacobian updating. It only has an effect for the Dense and Band solvers.

val set_res_mon : [> Nvector_serial.kind ] serial_session -> unit

Enables the nonlinear residual monitoring scheme that controls Jacobian updating. It only has an effect for the Dense and Band solvers.

val set_max_setup_calls : ('d, 'k) session -> int -> unit

Specifies the maximum number of nonlinear iterations between calls to the preconditioner setup function. Pass 0 to set the default (10).

val set_max_sub_setup_calls : [> Nvector_serial.kind ] serial_session -> int -> unit

Specifies the maximum number of nonlinear iterations between checks by the residual monitoring algorithm. Pass 0 to set the default (5). It only affects the Dense and Band solvers.

type eta_params = {
    egamma : float option; (* default = 0.9 *)    ealpha : float option; (* default = 2.0 *)
}

The parameters gamma and alpha in the formula for the Eisenstat and Walker Choice 2 for eta. Set either to None to specify its default value. The legal values are $0 < \mathtt{egamma} \leq 1.0 \wedge 1 < \mathtt{ealpha} \leq 2.0$.

type eta_choice = 
 | EtaChoice1 (* Eisenstat and Walker Choice 1 *) | EtaChoice2 of eta_params (* Eisenstat and Walker Choice 2 *) | EtaConstant of float option (* Constant (default = 0.1) *)

The eta parameter in the stopping criteria for the linear system solver.

val set_eta_choice : ('d, 'k) session -> eta_choice -> unit

Specifies the method for computing the value of the eta coefficient used in the calculation of the linear solver convergence tolerance.

val set_res_mon_const_value : ('d, 'k) session -> float -> unit

Specifies the constant value of omega when using residual monitoring. Pass 0.0 to specify the default value (0.9). The legal values are $0 < \mathtt{omega} < 1.0$.

val set_res_mon_params : ('d, 'k) session -> ?omegamin:float -> ?omegamax:float -> unit -> unit

Specifies the minimum and maximum values in the formula for omega. The legal values are $0 < \mathtt{omegamin} < \mathtt{omegamax} < 1.0$.

val set_no_min_eps : ('d, 'k) session -> unit

Specifies that the scaled linear residual tolerance (epsilon) is not bounded from below.

val set_min_eps : ('d, 'k) session -> unit

Specifies that the scaled linear residual tolerance (epsilon) is bounded from below. That is, the positive minimum value $0.01\mathtt{fnormtol}$ is applied to epsilon.

val set_max_newton_step : ('d, 'k) session -> float -> unit

Specifies the maximum allowable scaled length of the Newton step. Pass 0.0 to specify the default value $1000\lVert u_0 \rVert_{D_u}$, otherwise the given value must be greater than zero.

val set_max_beta_fails : ('d, 'k) session -> float -> unit

Specifies the maximum number of beta-condition failures in the line search algorithm. Pass 0.0 to specify the default (10).

val set_rel_err_func : ('d, 'k) session -> float -> unit

Specifies the relative error in computing $F(u)$, which is used in the difference quotient approximation of the Jacobian-vector product. Pass 0.0 to specify the default value ($\sqrt{\mathtt{unit\_roundoff}}$).

val set_func_norm_tol : ('d, 'k) session -> float -> unit

Specifies the stopping tolerance on the scaled maximum norm. It must be greater than zero. Pass 0.0 to specify the default value ($\mathtt{unit\_roundoff}^\frac{1}{3}$).

val set_scaled_step_tol : ('d, 'k) session -> float -> unit

Specifies the stopping tolerance on the minimum scaled step length, which must be greater than zero. Pass 0.0 to specify the default value ($\mathtt{unit\_roundoff}^\frac{1}{3}$).

val set_constraints : ('d, 'k) session -> ('d, 'k) Nvector.t -> unit

Specifies a vector defining inequality constraints for each component of the solution vector u. See Sundials.Constraint.

val set_sys_func : ('d, 'k) session -> ('d -> 'd -> unit) -> unit

Changes the system function. Allows solutions of several problems of the same size but with different functions.

#### Logging and error handling

val set_error_file : ('d, 'k) session -> Sundials.Logfile.t -> unit

Configure the default error handler to write messages to a file. By default it writes to Logfile.stderr.

val set_err_handler_fn : ('d, 'k) session -> (Sundials.Util.error_details -> unit) -> unit

Specifies a custom function for handling error messages. The handler must not fail: any exceptions are trapped and discarded.

val clear_err_handler_fn : ('d, 'k) session -> unit

Restores the default error handling function.

type print_level = 
 | NoInformation (* No information displayed. (0) *) | ShowScaledNorms (* At each nonlinear iteration, display the scaled Euclidean norm of the system function at the current iterate, the scaled norm of the Newton step (if no globalization strategy is used), and the number of function evaluations performed so far. (1) *) | ShowScaledDFNorm (* Additionally display $\lVert F(u) \rVert_{DF}$ if no globalization strategy is used, and $\lVert F(u)\rVert_{DF,\infty}$, otherwise. (2) *) | ShowGlobalValues (* Additionally display the values used by the global strategy and statistical information for the linear solver. (3) *)

Increasing levels of verbosity for informational messages.

val set_print_level : ('d, 'k) session -> print_level -> unit

Sets the level of verbosity of informational messages.

val set_info_file : ('d, 'k) session ->       ?print_level:print_level -> Sundials.Logfile.t -> unit

Write informational (non-error) messages to the given file. By default they are written to Logfile.stdout. The optional argument is a convenience for invoking Kinsol.set_print_level.

val set_info_handler_fn : ('d, 'k) session -> (Sundials.Util.error_details -> unit) -> unit

Specifies a custom function for handling informational (non-error) messages. The error_code field of Util.error_details is 0 for such messages. The handler must not fail: any exceptions are trapped and discarded.

val clear_info_handler_fn : ('d, 'k) session -> unit

Restores the default information handling function.

val set_return_newest : ('d, 'k) session -> bool -> unit

Specifies whether fixed-point iteration should return the newest iteration or the iteration consistent with the last function evaluation. The default values is false.

val set_damping : ('d, 'k) session -> float -> unit

Sets the damping parameter for the fixed point or Picard iteration.

To applying damping, the given beta value must be greater than 0 and less than 1. Damping is disabled if beta >= 1. The default value is 1.

val set_damping_aa : ('d, 'k) session -> float -> unit

Set the Anderson acceleration damping parameter.

To applying damping, the given beta value must be greater than 0 and less than 1. Damping is disabled if beta >= 1. The default value is 1.

val set_delay_aa : ('d, 'k) session -> float -> unit

Sets the number of iterations to delay the start of Anderson acceleration. The default value is 0.

### Querying the solver (optional output functions)

val get_work_space : ('d, 'k) session -> int * int

Returns the sizes of the real and integer workspaces.

• Returns (real_size, integer_size)
• See Sundials: KINGetWorkSpace
val get_num_func_evals : ('d, 'k) session -> int

Returns the number of evaluations of the system function.

val get_num_nonlin_solv_iters : ('d, 'k) session -> int

Returns the cumulative number of nonlinear iterations.

val get_num_beta_cond_fails : ('d, 'k) session -> int

Returns the number of beta-condition failures.

val get_num_backtrack_ops : ('d, 'k) session -> int

Returns the number of backtrack operations (step length adjustments) performed by the line search algorithm.

val get_func_norm : ('d, 'k) session -> float

Returns the scaled Euclidiean l2 norm of the nonlinear system function $F(u)$ evaluated at the current iterate.

val get_step_length : ('d, 'k) session -> float

Returns the scaled Euclidiean l2 norm of the step used during the previous iteration.

### Exceptions

exception IllInput

An input parameter was invalid.

exception LineSearchNonConvergence

Line search could not find an iterate sufficiently distinct from the current one, or an iterate satisfying the sufficient decrease condition. The latter could mean that the current iterate is “close” to an approximate solution, but that the difference approximation of the matrix-vector product is inaccurate, or that scsteptol (Kinsol.set_scaled_step_tol) is too large.

exception MaxIterationsReached

The maximum number of nonlinear iterations has been reached.

exception MaxNewtonStepExceeded

Five consecutive steps exceed the maximum newton step. That is, the five steps satisfy the inequality $\\|D_u p\\|_{L2} > 0.99 \mathtt{mxnewtstep}$, where $p$ denotes the current step and mxnewtstep is a scalar upper bound on the scaled step length (see Kinsol.set_max_newton_step). It could be that $\\| D_F F(u)\\|_{L2}$ is bounded from above by a positive value or that mxnewtstep is too small.

exception LineSearchBetaConditionFailure

The line search algorithm could not satisfy the “beta-condition” for mxnbcf + 1 nonlinear iterations. The failures need not occur in consecutive iterations. They may indicate that the algorithm is making poor progress.

exception LinearSolverNoRecovery

The Kinsol.Spils.prec_solve_fn callback raised Sundials.RecoverableFailure but the preconditioner is already current.

exception LinearSolverInitFailure

Linear solver initialization failed.

exception LinearSetupFailure of exn option

The Kinsol.Spils.prec_setup_fn callback failed unrecoverably. If possible, the exception in the underlying linear solver is specified. It is typically one of Sundials_LinearSolver.ZeroInDiagonal, Sundials_LinearSolver.PSetFailure, or Sundials_LinearSolver.PackageFailure.

exception LinearSolveFailure of exn option

Either Kinsol.Spils.prec_solve_fn failed unrecoverably or the linear solver encountered an error condition. If possible, the exception in the underlying linear solver is specified. It is typically one of Sundials_LinearSolver.ZeroInDiagonal, Sundials_LinearSolver.ATimesFailure, Sundials_LinearSolver.PSolveFailure, Sundials_LinearSolver.GSFailure, Sundials_LinearSolver.QRSolFailure, or Sundials_LinearSolver.PackageFailure.

exception SystemFunctionFailure

The Kinsol.sysfn callback failed unrecoverably.

exception FirstSystemFunctionFailure

The Kinsol.sysfn callback raised Sundials.RecoverableFailure when first called.

exception RepeatedSystemFunctionFailure

The Kinsol.sysfn callback raised Sundials.RecoverableFailure repeatedly. No recovery is possible.

exception MissingLinearSolver

A linear solver is required but was not specified.

exception VectorOpErr`

A fused vector operation failed.