Nonlinear Solver#

A factory for creating nonlinear solvers.

Nonlinear solvers are used within implicit time integration schemes to drive the residual to zero and thereby solve for the primary variable at the new time.

solver-typed-spec

Warning

“JFNK”, “line search”, and “continuation” methods have not been beaten on as much as other methods. “nka_ls_ats” is somewhat deprecated and probably shouldn’t be used. Prefer “nka” for simple problems, “nka_bt_ats” for freeze-thaw problems or other problems with strong nonlinearities, and “Newton” when you have a good Jacobian. While “nox” hasn’t been used extensively, it may be quite useful.

Solver: Newton and Inexact Newton#

Straightforward Newton/Inexact Newton solver.

The classical Newton method works well for cases where Jacobian is available and corresponds to a stable (e.g. upwind) discretization. The inexact Newton methods work for cases where the discrete Jacobian is either not available, or not stable, or computationally expensive. The discrete Jacobian is replaced by a stable approximation of the continuum Jacobian. The choice between exact and inexact is not made by the Solver, but instead by the PK. Both use the ApplyPreconditioner() method – if this applies the true Jacobian, then the method is Newton. If it applies an appoximation, it is inexact Newton.

solver-newton-spec

  • “nonlinear tolerance” [double] 1.e-6 defines the required error tolerance. The error is calculated by a PK.

  • “monitor” [string] monitor update specifies control of the nonlinear residual. The available options are “monitor update” and “monitor residual”.

  • “limit iterations” [int] 50 defines the maximum allowed number of iterations.

  • “diverged tolerance” [double] 1.e10 defines the error level indicating divergence of the solver. The error is calculated by a PK.

  • “max du growth factor” [double] 1.e5 allows the solver to identify divergence pattern on earlier iterations. If the maximum norm of the solution increment changes drastically on two consecutive iterations, the solver is terminated.

  • “max error growth factor” [double] 1.e5 defines another way to identify divergence pattern on earlier iterations. If the PK-specific error changes drastically on two consecutive iterations, the solver is terminated.

  • “max divergent iterations” [int] 3 defines another way to identify divergence pattern on earlier iterations. If the maximum norm of the solution increment grows on too many consecutive iterations, the solver is terminated.

  • “make one iteration” [bool] false require at least one iteration to be performed before declaring success. This options makes any effect only when “monitor residual” is choose.

  • “modify correction” [bool] true allows a PK to modify the solution increment. One example is a physics-based clipping of extreme solution values.

  • “stagnation iteration check” [int] 8 determines the number of iterations before the stagnation check is turned on. The stagnation happens when the current l2-error exceeds the initial l2-error.

Solver: Jacobian-Free Newton Krylov#

Decorator for using a Solver with JFNK as the preconditioner.

Jacobian-Free Newton Krylov uses a finite difference scheme to approximate the action of the Jacobian matrix, then uses a Krylov method (which only needs the action of the Jacobian and not the Jacobian itself) to calculate the action of the inverse of the Jacobian, thereby providing a Newton-like update. As the linear Krylov scheme converges to the inverse action, the nonlinear solution converges to the same solution as a true Newton method.

This implementation simply replaces a SolverFnBase’s ApplyPreconditioner() with a new ApplyPreconditioner() which uses the Krylov method with the action of the forward operator to (hopefully) improve, relative to the supplied approximate inverse, the estimate of the inverse.

solver-jfnk-spec

  • “nonlinear solver” [solver-typed-spec] The outer nonlinear solver to use.

  • “inverse” [inverse-typed-spec] The Krylov method to use.

  • “JF matrix parameters” [jf-matrix-spec] See jf-matrix-spec

<Parameter name="solver type" type="string" value="JFNK"/>
<ParameterList name="JFNK parameters">
  <Parameter name="typical solution value" type="double" value="1.0"/>

  <ParameterList name="JF matrix parameters">
    <Parameter name="finite difference epsilon" type="double" value="1.0e-8"/>
    <Parameter name="method for epsilon" type="string" value="Knoll-Keyes L2"/>
  </ParameterList>

  <ParameterList name="nonlinear solver">
    <Parameter name="nonlinear tolerance" type="double" value="1.0e-05"/>
    <Parameter name="diverged tolerance" type="double" value="1.0e+10"/>
    <Parameter name="limit iterations" type="int" value="20"/>
    <Parameter name="max divergent iterations" type="int" value="3"/>
  </ParameterList>

  <ParameterList name="linear operator">
    <Parameter name="iterative method" type="string" value="gmres"/>
    <ParameterList name="gmres parameters">
      ...
    </ParameterList>
  </ParameterList>
</ParameterList>
</ParameterList>

The Jacobian-Free Matrix operator, which is used to estimate the action of the Jacobian.

A variety of methods are available for choosing the epsilon used to approximate the action of the Jacobian. They are documented in Knoll & Keyes 2004 paper.

..todo:: Document these

jf-matrix-spec

  • “typical solution value” [double] 100 Used in relative action approximations. OPTION NOT IMPLEMENTED

  • “finite difference epsilon” [double] 1.e-8 defines the base finite difference epsilon.

  • “method for epsilon” [string] defines a method for calculating finite difference epsilon. Available option is “Knoll-Keyes”, “Knoll-Keyes L2”, “Brown-Saad”. See Knoll

Solver: Nonlinear Continuation#

A very simple nonlinear continuation method.

Continuation methods are useful when the nonlinearity can be controlled by a single simple parameter. In this method, the nonlinear problem is solved with a less-nonlinear value of the parameter, and the solution of that is used as the initial guess to solve a harder problem. As each successive problem is solved, the continuation parameter is changed closer and closer to the true value.

Few if any PKs support this method currently – it requires the PK to provide more interface about how to update the continuation parameter.

solver-continuation-spec

  • “nonlinear tolerance” [double] 1.e-6 defines the required error tolerance. The error is calculated by a PK.

  • “number of continuation steps” [int] 5 How many steps to take from initial parameter to final parameter.

  • “inner solver” [solver-typed-spec] A Solver, used at each step.

Solver: Nonlinear Krylov Acceleration#

Nonlinear Krylov Acceleration as a nonlinear solver.

Uses the Nonlinear Krylov acceleration method of Carlson and Miller to do effectively a multivariant secant method, accelerating the solution of a nonlinear solve. This method can be significantly faster than Newton, especially with an approximate Jacobian.

Calef et al. “Nonlinear Krylov acceleration applied to a discrete ordinates formulation of the k-eigenvalue problem.” JCP 238 (2013): 188-209.

N. N. Carlson, K. Miller, Design and application of a gradient-weighted moving finite element code II: In two dimensions, SIAM J. Sci. Comput. 19 (3) (1998) 766–798.

solver-nka-spec

  • “nonlinear tolerance” [double] 1.e-6 Defines the required error tolerance. The error is calculated by a PK.

  • “monitor” [string] monitor update Specifies control of the nonlinear residual. The available options are “monitor update”, “monitor residual”, “monitor preconditioned residual”, “monitor l2 residual”, and “monitor preconditioned l2 residual”.

  • “limit iterations” [int] 20 Defines the maximum allowed number of iterations.

  • “diverged tolerance” [double] 1.e10 Defines the error level indicating divergence of the solver. The error is calculated by a PK. Set to a negative value to ignore this check.

  • “diverged l2 tolerance” [double] 1.e10 Defines another way to identify divergence of the solver. If the relative l2 (little l) norm of the solution increment is above this value, the solver is terminated. Set to a negative value to ignore this check.

  • “diverged pc tolerance” [double] 1e10 Defines another way to identify divergence of the solver. If the relative maximum norm of the solution increment (with respect to the initial increment) is above this value, the solver is terminated. Set to a negative value to ignore this check.

  • “diverged residual tolerance” [double] 1e10 Defines another way to identify divergence of the solver. If the relative l2 norm of the residual (with respect to the initial residual) is above this value, the solver is terminated. Set to a negative value to ignore this check.

  • “max du growth factor” [double] 1e5 Allows the solver to identify divergence pattern on earlier iterations. If the maximum norm of the solution increment changes drastically on two consecutive iterations, the solver is terminated.

  • “max error growth factor” [double] 1e5 Defines another way to identify divergence pattern on earlier iterations. If the PK-specific error changes drastically on two consecutive iterations, the solver is terminated.

  • “max divergent iterations” [int] 3 Defines another way to identify divergence pattern on earlier iterations. If the maximum norm of the solution increment grows on too many consecutive iterations, the solver is terminated.

  • “make one iteration” [bool] false require at least one iteration to be performed before declaring success. This options makes any effect only when “monitor residual” is choose.

  • “modify correction” [bool] false Allows a PK to modify the solution increment. One example is a physics-based clipping of extreme solution values.

  • “lag iterations” [int] 0 Delays the NKA acceleration, but updates the Krylov space.

  • “max nka vectors” [int] 10 Defines the maximum number of consecutive vectors used for a local space.

  • “nka vector tolerance” [double] 0.05 Defines the minimum allowed orthogonality between vectors in the local space. If a new vector does not satisfy this requirement, the space is modified.

Solver: Anderson Acceleration#

Anderson acceleration as a nonlinear solver.

This is a variation of the GMRES solver for nonlinear problems.

solver-aa-spec

  • “nonlinear tolerance” [double] 1.e-6 Defines the required error tolerance. The error is calculated by a PK.

  • “limit iterations” [int] 20 Defines the maximum allowed number of iterations.

  • “diverged tolerance” [double] 1.e10 Defines the error level indicating divergence of the solver. The error is calculated by a PK. Set to a negative value to ignore this check.

  • “diverged l2 tolerance” [double] 1.e10 Defines another way to identify divergence of the solver. If the relative L2 norm of the solution increment is above this value, the solver is terminated. Set to a negative value to ignore this check.

  • “max du growth factor” [double] 1e5 Allows the solver to identify divergence pattern on earlier iterations. If the maximum norm of the solution increment changes drastically on two consecutive iterations, the solver is terminated.

  • “max divergent iterations” [int] 3 Defines another way to identify divergence pattern on earlier iterations. If the maximum norm of the solution increment grows on too many consecutive iterations, the solver is terminated.

  • “max aa vectors” [int] 10 Defines the maximum number of consecutive vectors used for a local space.

  • “modify correction” [bool] false Allows a PK to modify the solution increment. One example is a physics-based clipping of extreme solution values.

  • “relaxation parameter” [double] 1 Damping factor for increment.

Solver: NKA with Line Search, ATS#

Solver: NKA with backtracking, ATS#

Nonlinear solve using NKA with a heuristic based backtracking.

Whereas line search uses a formal minimization method, backtracking simply uses a heuristic multiplier on \(\alpha\) to find a correction that sufficiently reduces the residual. This can be significantly faster than the full minimization problem, and finding the true minimum may not be as important as simply doing better and going on to the next nonlinear iteration.

This is the workhorse for hard ATS problems, as it is usually rather efficient, even in problems where the linear solve results in a correction that is way too large (e.g. for steep nonlinearities such as phase change).

Note this always monitors the residual, and the correction is always modified.

solver-nka-bt-ats-spec

  • “nonlinear tolerance” [double] 1.e-6 Defines the required error tolerance. The error is calculated by a PK.

  • “limit iterations” [int] 20 Defines the maximum allowed number of iterations.

  • “diverged tolerance” [double] 1.e10 Defines the error level indicating divergence of the solver. The error is calculated by a PK. Set to a negative value to ignore this check.

  • “nka lag iterations” [int] 0 Delays the NKA acceleration, but updates the Krylov space.

  • “max nka vectors” [int] 10 Defines the maximum number of consecutive vectors used for a local space.

  • “nka vector tolerance” [double] 0.05 Defines the minimum allowed orthogonality between vectors in the local space. If a new vector does not satisfy this requirement, the space is modified.

  • “backtrack tolerance” [double] 0. Require a reduction of at least this much in the residual norm before accepting a correction.

  • “backtrack factor” [double] 0.5 Multiply the correction by this factor each backtracking step. Note, should be in (0, 1)

  • “backtrack monitor” [string] monitor either What norm is checked to determine whether backtracking has improved the residual or not? One of “monitor enorm”, “monitor L2 residual”, or ‘monitor either”

  • “backtrack max steps” [int] 10 Controls how many multiples of the backtrack factor are applied before declaring failure.

  • “backtrack max total steps” [int] 1e6 Controls how many total backtrack steps may be taken before declaring failure.

  • “backtrack lag iterations” [int] 0 Delay requiring a reduction in residual for this many nonlinear iterations.

  • “backtrack last iteration” [int] 1e6 Stop requiring a reductiontion in residual after this many nonlinear iterations.

  • “backtrack fail on bad search direction” [bool] false If backtracking for the full number of “backtrack max steps” is taken, and the residual norm has still not be reduced suffiently, this determines the behavior. If true, the solver declares failure. If false, it takes the bad step anyway and hopes to recover in later iterates.

IF

  • “Anderson mixing” [bool] false If true, use Anderson mixing instead of NKA.

THEN

  • “relaxation parameter” [double] 0.7 The relaxation parameter for Anderson mixing.

END

Solver: NOX#

Calls Nox nonlinear solvers/JFNK.

The interface to Trilinos NOX solver is as follows:

<Parameter name="solver type" type="string" value="nox"/>
  <ParameterList name="nox parameters">
    <Parameter name="typical solution value" type="double" value="1.0"/>

    <ParameterList name="JF matrix parameters">
      <Parameter name="finite difference epsilon" type="double" value="1.0e-8"/>
      <Parameter name="method for epsilon" type="string" value="Knoll-Keyes L2"/>
    </ParameterList>

    <ParameterList name="nonlinear solver">
      <Parameter name="solver type" type="string" value="Newton"/>
      <ParameterList name="Newton parameters">
        ...
      </ParameterList>
    </ParameterList>

    <ParameterList name="linear operator">
      <Parameter name="iterative method" type="string" value="gmres"/>
      <ParameterList name="gmres parameters">
        ...
      </ParameterList>
    </ParameterList>
  </ParameterList>
</ParameterList>