Path Tracker

PathTracker

The PathTracker combines the path tracking (with CoreTracker) with an endgame routine. The endgame is the name for special algorithms the end of the path tracking. These enable to detect if a path is diverging or if it ends in a singular solution. The PathTracker is more opinionated than the CoreTracker and implements additional logic to handle numerical difficult solutions. In particular it always reparametrizes a solution path to use a logarithmic time scale, i.e., $x(t) → x(e^{-s})$ and we track for $s$ from $0$ to $∞$.

In order to construct a PathTracker it is recommended to use the pathtracker and pathtracker_startsolutions helper functions. With a PathTracker constructed you can track a single path using the track method. The result of this will be a PathResult.

The PathTracker assumes that the provided homotopy H is defined in such a way that H(x,1) is the start system and H(x,0) the target system. During the path tracking an approximation of the valuation of a Puiseux series expansion of the solution is computed. This is used to decide whether a path is diverging. Before a certain treshold (s_always_consider_valuation) this approximation is only trusted if a path gives some sign of ill-conditioning. To compute singular solutions the Cauchy endgame is used which is based on Cauchy's integral formula. For this we have to track solutions along a loop around the origin. The number of loops necessary to arrive back at the start point is called the winding number.

Options

The path tracker accepts all options which CoreTracker accepts. Furthermore the following options are accepted:

• at_infinity_check: This is true if the provided start system is an affine polynomial system.
• endgame_start (default 2.0): The value of s where the endgame is started earliest.
• max_winding_number (default 12): The maximal winding number tried in the Cauchy endgame.
• min_accuracy (default 1e-5): The PathTracker automatically lowers the desired accuracy automatically to min_accuracy if path tracking would fail othwerwise (since the desired cannot be reached)
• min_cond_eg (default 1e5): The minimal condition number before the Cauchy endgame is started or a path is cut off.
• min_step_size_before_eg (default exp2(-40)): The minimal allowed step size before the endgame starts.
• min_step_size_eg (default exp2(-120)): The minimal allowed step size during the endgame. This is also control what is considered ∞ for the path tracking.
• s_always_consider_valuation (default -log(1e-16)) A threshold after which we always consider the valuation.
• samples_per_loop (default8`): The number of samples used during the endgame.
• precision_strategy (default :adaptive_finite): This controls whether H(x,t) is possibly evaluated with higher than machine precision during the endgame (the Jacobian is always computed with machine precision). The :adaptive_finite allows this only if we are optimistic that we can still obtain a finite solution. Other options are :adaptive_never where this is never allowed and :adaptive_always where it is always enabled. ``

pathtracker_startsolutions(args...; kwargs...)

Construct a PathTracker and start solutions in the same way solve does it. This also takes the same input arguments as solve. This is convenient if you want to investigate single paths.

pathtracker(args...; kwargs...)

Construct a PathTracker in the same way solve does it. This also takes the same input arguments as solve with the exception that you do not need to specify startsolutions.

Examples

Obtain single solution

We want to construct a path tracker to track a parametrized system f with parameters p from the parameters a to b.

tracker = pathtracker(f, parameters=p, p₁=a, p₀=b)

You then can obtain a single solution at b by using

x_b = solution(track(tracker, x_a))

track(tracker::PathTracker, x₁;
        path_number=nothing,
        details::Symbol=:default,
        start_parameters = nothing,
        target_parameters = nothing)

Track the path x(t) with start solution x₁ from $1$ towards $0$. Returns a PathResult.

The details options controls the level of details of the informations available in the PathResult. If tracker uses a parameter homotopy you can set the start and target parameters by setting the corresponding fields. To investigate the behaviour of a particular take a look at path_info.

PathResult{V<:AbstractVector}

A PathResult is the result of tracking of a path with track using a PathTracker.

Fields

• return_code: See the list of return codes below.
• solution::V: The solution vector.
• t::Float64: The value of t at which solution was computed. Note that if return_code is :at_infinity, then t is the value when this was decided.
• accuracy::Float64: An approximation of $||x-x̄||$ where $x$ is the computed solution and $x̄$ is the true solution.
• residual::Float64: The value of the infinity-norm of H(solution, 0).
• multiplicity::Union{Nothing, Int} is the multiplicity of the solution. This is only assigned by singular.
• condition_jacobian::Union{Nothing, Float64}: This is the condition number of the row-equilibrated Jacobian at the solution. A high condition number indicates a singularity.
• winding_number:Union{Nothing, Int}: The estimated winding number. This is a lower bound on the multiplicity of the solution.
• start_solution::Union{Nothing, Int}: The start solution of the path.
• accepted_steps::Int: The number of accepted steps during the path tracking.
• rejected_steps::Int: The number of rejected steps during the path tracking.
• valuation::Union{Nothing, Vector{Float64}}: An approximation of the valuation of the Puiseux series expansion of x(t).
• valuation_accuracy::Union{Nothing, Vector{Float64}}: An estimate of the accuracy of the valuation of the Puiseux series expansion of x(t).

Return codes

These is the list of possible return codes:

• :success: The PathTracker obtained a solution.
• :at_infinity: The PathTracker stopped the tracking of the path since it determined that that path is diverging towards infinity.
• :terminated_callback: One of the optional PathTracker callbacks terminated the tracking.
• :terminated_max_iters: The PathTracker terminated since it reached the limit accuracy.
• :terminated_invalid_startvalue: The PathTracker terminated since the provided start value is invalid.
• :terminated_step_size_too_small: The PathTracker terminated since the step size became smaller than the provided threshold.
• :terminated_accuracy_limit: The PathTracker terminated since the problem was too ill-conditioned to be tracked further with the desired minimal accuracy.
• :terminated_ill_conditioned: The PathTracker terminated since the Jacobian of the homotopy was too ill-conditioned.
• :post_check_failed: The verification of a non-singular solution failed.

Constructors

 PathResult(tracker::PathTracker,
            start_solution=nothing,
            path_number::Union{Nothing,Int}=nothing;
            details=:default)

Construct a PathResult using the current state of the PathTracker. Possible values for details are :minimal (minimal details), :default (default) and :extensive (all information possible).

solution(r::PathResult)

Get the solution of the path.

accuracy(r::PathResult)

Get the accuracy of the solution. This is an estimate of the (relative) distance to the true solution.

residual(r::PathResult)

Get the residual of the solution $x$ of the path, i.e., $||H(x, 0)||₂$.

winding_number(tracker::PathTracker)

Obtain the estimate of the winding number computed by the PathTracker. Returns nothing if the Cauchy endgame was not run.

multiplicity(P::PathResult)

Returns the multiplicity of P.

condition_jacobian(r::PathResult)

Return the condition number of the Jacobian of the result.

cond(r::PathResult)

Return the condition number of the Jacobian of the result.

start_solution(r::PathResult)

Get the start solution of the path.

is_real(r::PathResult; tol=1e-6)

We consider a result as real if the 2-norm of the imaginary part of the solution is at most tol.

is_success(r::PathResult)

Checks whether the path is successfull.

is_failed(r::PathResult)

Checks whether the path failed.

is_affine(pathresult)

Return`s true if the solution is an affine vector.

is_projective(r::PathResult)

Return`s true if the solution is a projective vector.

is_at_infinity(r::PathResult)

Checks whether the path goes to infinity.

is_singular(r::PathResult; tol=1e10)

Checks whether the path result is singular. This is true if the multiplicity is larger than 1 or if the condition number of the Jacobian is larger than tol.

is_nonsingular(r::PathResult; tol=1e10)

Checks whether the path result is non-singular. This is true if it is not singular.

track!(tracker::PathTracker, x₁)::PathTrackerStatus.states

Track the path x(t) with start solution x₁ from $1$ towards $0$. Returns a PathTrackerStatus.states.

start_parameters!(tracker::PathTracker, p)

Set the start parameters of the homotopy in in tracker to p.

target_parameters!(tracker::PathTracker, p)

Set the target parameters of the homotopy in in tracker to p.

enum PathTrackerStatus

The possible states a PathTracker can be in:

• PathTrackerStatus.tracking
• PathTrackerStatus.success
• PathTrackerStatus.at_infinity
• PathTrackerStatus.excess_solution
• PathTrackerStatus.post_check_failed
• PathTrackerStatus.terminated_accuracy_limit
• PathTrackerStatus.terminated_ill_conditioned
• PathTrackerStatus.terminated_invalid_startvalue
• PathTrackerStatus.terminated_max_winding_number
• PathTrackerStatus.terminated_max_iters
• PathTrackerStatus.terminated_step_size_too_small

is_success(S::CoreTrackerStatus.states)

Returns true if S indicates a success in the path tracking.

is_success(result::CoreTrackerResult)

Returns true if the path tracking was successfull.

is_success(status::PathTrackerStatus.states)

Returns true if status indicates a success in tracking.

is_success(r::PathResult)

Checks whether the path is successfull.

is_success(result::MonodromyResult)

Returns true if the monodromy computation achieved its target solution count.

is_success(status::PathTrackerStatus.states)

Returns true if status indicates that a path diverged towards infinity.

is_at_infinity(r::PathResult)

Checks whether the path goes to infinity.

is_invalid_startvalue(S::CoreTrackerStatus.states)

Returns true if S indicates that the path tracking got terminated since the start value was not a zero.

is_invalid_startvalue(status::PathTrackerStatus.states)

Returns true if the provided start value was not valid.

is_failed(r::PathResult)

Checks whether the path failed.

is_terminated_callback(status::PathTrackerStatus.states)

Returns true if the provided callback indicated a termination of the path.

is_tracking(S::CoreTrackerStatus.states)

Returns true if S indicates that the path tracking is not yet finished.

is_tracking(status::PathTrackerStatus.states)

Returns true if status indicates the tracking is not going on.