Ariadne.jl

newton_krylov!(F!, u₀::AbstractArray, p = nothing, M::Int = length(u₀); kwargs...)

Takes an in-place residual function F!(res, u, p).

Arguments

• F!: F!(res, u, p) solves res = F(u) = 0
• u₀: Initial guess
• p: Parameters
• M: Length of the output of F!. Defaults to length(u₀)

Keyword Arguments

• tol_rel: Relative tolerance
• tol_abs: Absolute tolerance
• max_niter: Maximum number of iterations
• forcing: Maximum forcing term for inexact Newton. If nothing an exact Newton method is used.
• linesearch!: Line search strategy. Must be a subtype of AbstractLineSearch.
• verbose::Int: Verbosity level
• M::Union{Nothing, Function}: If provided, M(ws.J) is passed as a keyword argument to the Krylov solver.
• N::Union{Nothing, Function}: If provided, N(ws.J) is passed as a keyword argument to the Krylov solver.
• krylov_kwargs: Keyword arguments passed to the Krylov solver.
• callback: A function called after each Newton iteration with signature callback(u, res, norm_res).

newton_krylov!(F!, u, p, res; kwargs...)

Takes an in-place residual function F!(res, u, p).

Arguments

• F!: F!(res, u, p) solves res = F(u) = 0
• u: Initial guess (modified in-place)
• p: Parameters
• res: Temporary for residual

Keyword Arguments

• tol_rel: Relative tolerance
• tol_abs: Absolute tolerance
• max_niter: Maximum number of iterations
• forcing: Maximum forcing term for inexact Newton. If nothing an exact Newton method is used.
• linesearch!: Line search strategy. Must be a subtype of AbstractLineSearch.
• verbose::Int: Verbosity level
• M::Union{Nothing, Function}: If provided, M(ws.J) is passed as a keyword argument to the Krylov solver.
• N::Union{Nothing, Function}: If provided, N(ws.J) is passed as a keyword argument to the Krylov solver.
• krylov_kwargs: Keyword arguments passed to the Krylov solver.
• callback: A function called after each Newton iteration with signature callback(u, res, norm_res).

newton_krylov!(ws::NewtonKrylovWorkspace, u; kwargs...)

Updates ws.u with the initial guess u and then calls newton_krylov!(ws; kwargs...).

Arguments

• F!: F!(res, u, p) solves res = F(u) = 0
• u: Initial guess (must have the same shape as ws.u)

Keyword Arguments

• tol_rel: Relative tolerance
• tol_abs: Absolute tolerance
• max_niter: Maximum number of iterations
• forcing: Maximum forcing term for inexact Newton. If nothing an exact Newton method is used.
• linesearch!: Line search strategy. Must be a subtype of AbstractLineSearch.
• verbose::Int: Verbosity level
• M::Union{Nothing, Function}: If provided, M(ws.J) is passed as a keyword argument to the Krylov solver.
• N::Union{Nothing, Function}: If provided, N(ws.J) is passed as a keyword argument to the Krylov solver.
• krylov_kwargs: Keyword arguments passed to the Krylov solver.
• callback: A function called after each Newton iteration with signature callback(u, res, norm_res).

newton_krylov!(ws; kwargs...)

Arguments

• ws: Pre-allocated NewtonKrylovWorkspace

Keyword Arguments

• tol_rel: Relative tolerance
• tol_abs: Absolute tolerance
• max_niter: Maximum number of iterations
• forcing: Maximum forcing term for inexact Newton. If nothing an exact Newton method is used.
• linesearch!: Line search strategy. Must be a subtype of AbstractLineSearch.
• verbose::Int: Verbosity level
• M::Union{Nothing, Function}: If provided, M(ws.J) is passed as a keyword argument to the Krylov solver.
• N::Union{Nothing, Function}: If provided, N(ws.J) is passed as a keyword argument to the Krylov solver.
• krylov_kwargs: Keyword arguments passed to the Krylov solver.
• callback: A function called after each Newton iteration with signature callback(u, res, norm_res).

newton_krylov(F, u₀::AbstractArray, p = nothing, M::Int = length(u₀); kwargs...)

Takes a out-of-place residual function F(u, p).

Arguments

• F: res = F(u₀, p) solves res = F(u₀) = 0
• u₀: Initial guess
• p: Parameters
• M: Length of the output of F. Defaults to length(u₀).

Keyword Arguments

• tol_rel: Relative tolerance
• tol_abs: Absolute tolerance
• max_niter: Maximum number of iterations
• forcing: Maximum forcing term for inexact Newton. If nothing an exact Newton method is used.
• linesearch!: Line search strategy. Must be a subtype of AbstractLineSearch.
• verbose::Int: Verbosity level
• M::Union{Nothing, Function}: If provided, M(ws.J) is passed as a keyword argument to the Krylov solver.
• N::Union{Nothing, Function}: If provided, N(ws.J) is passed as a keyword argument to the Krylov solver.
• krylov_kwargs: Keyword arguments passed to the Krylov solver.
• callback: A function called after each Newton iteration with signature callback(u, res, norm_res).

NewtonKrylovWorkspace

Pre-allocated workspace for newton_krylov!. Holds the residual buffer, negated-residual buffer, Jacobian operator (with its Enzyme caches), and the Krylov solver workspace so that no intermediate arrays are allocated during the Newton iteration.

Constructor

NewtonKrylovWorkspace(F!, u, p, res, alg=Val(:gmres); assume_p_const = false)

• F!: in-place residual function F!(res, u, p)
• u: initial-guess array (used as template; the workspace holds a reference to it)
• p: parameters
• res: pre-allocated residual buffer
• algo: Krylov algorithm symbol (e.g. :gmres, :fgmres) passed as a Val.
• assume_p_const: passed through to JacobianOperator

Example

    ws = NewtonKrylovWorkspace(F!, u, p, res, Val(:gmres))
    newton_krylov!(ws)

    # To change the initial guess, pass it to newton_krylov!:
    newton_krylov!(ws, u_new)    

AbstractLineSearch

Line search updates ws.u in-place along the Newton direction d and calls evaluate!(ws) to refresh ws.res and obtain the new residual norm.

Implemented variants

• NoLineSearch
• BacktrackingLineSearch

Custom line searches

struct CustomLineSearch <: AbstractLineSearch
    # parameters for the line search
end

function (ls::CustomLineSearch)(ws, norm_res_prior, d)
    # update ws.u
    ws.u .+= d # for example, take the full Newton step
    return evaluate!(ws)
end

NoLineSearch()

A line search that does not perform any line search: it simply takes the full Newton step.

BacktrackingLineSearch(; n_iter_max = 10)

References

• Kelley, C. T. (2022). Solving nonlinear equations with iterative methods: Solvers and examples in Julia. Society for Industrial and Applied Mathematics.
• https://github.com/ctkelley/SIAMFANLEquations.jl

Forcing

Implements forcing for inexact Newton-Krylov. The equation $‖F′(u)d + F(u)‖ <= η * ‖F(u)‖$ gives the inexact Newton termination criterion.

Implemented variants

• Fixed
• EisenstatWalker

Fixed(η = 0.1)

EisenstatWalker(η_max = 0.999, γ = 0.9)

JacobianOperator

Efficient implementation of J(f,x,p) * v and v * J(f, x,p)'

BatchedJacobianOperator{N}

Ariadne.evaluate!(ws::NewtonKrylovWorkspace) -> norm_res

Evaluate F!(ws.res, ws.u, ws.p) in-place and return norm(ws.res).