Tracker
Tracker is a data structure to track for a given AbstractHomotopy $H(x,t)$ a solution $x$ from $t₁ ∈ ℂ$ to $t₀ ∈ ℂ$, i.e., $H(x,t₁) = 0$ and $x'$ with $H(x',t₀) = 0$ is returned. This is done by following an implicitly defined smooth path $x(t)$ using a predictor-corrector scheme. In particular, it is assumed that for all $t$ on the line segment between $t₁$ and $t₀$ the Jacobian $H_x(x(t),t)$ has full column-rank. The algorithm uses as an predictor a Padé approximant of order (2,1) and as a corrector Newton's method. The details of the algorithm are described in the article [Tim20].
Constructor and Options
HomotopyContinuation.Tracker — TypeTracker(H::AbstractHomotopy;
options = TrackerOptions(),
weighted_norm_options = WeightedNormOptions())Construct a tracker for the given homotopy H. The algorithm computes along the path $x(t)$ the local derivatives up to order 4. For options see also TrackerOptions. The algorithm uses as a weighted infinity norm to measure distances. See also WeightedNorm.
Example
We want to solve the system
@var x y t
F = System([x^2 + y^2 - 3, 2x^2 + 0.5x*y + 3y^2 - 2])using a total degree homotopy and Tracker.
# construct start system and homotopy
G = System(im * [x^2 - 1, y^2 - 1])
H = StraightLineHomotopy(G, F)
start_solutions = [[1,1], [-1,1], [1,-1], [-1,-1]]
# construct tracker
tracker = Tracker(H)
# track each start solution separetely
results = track.(tracker, start_solutions)
println("# successfull: ", count(is_success, results))We see that we tracked all 4 paths successfully.
# successfull: 4HomotopyContinuation.TrackerOptions — TypeTrackerOptions(; options...)The set of options for a Tracker.
Options
automatic_differentiation = 1: The valueautomatic_differentiationdetermines up to which order the derivative is computed using automatic differentiation. Otherwise numerical differentiation is used. The automatic differentiation results in additional compilation time, however for numerically challenging paths it is strongly recommended to useautomatic_differentiation = 3.max_steps = 10_000: The maximal number of steps a tracker attemptsmax_step_size = Inf: The maximal size of a stepmax_initial_step_size = Inf: The maximal size of the first stepmin_step_size = 1e-48: The minimal step size. If a smaller step size would be necessary, then the tracking gets terminated.extended_precision = true: Whether to allow for the use of extended precision, if necessary, in some computations. This can greatly improve the ability to track numerically difficult paths.terminate_cond = 1e13: If the relative component-wise condition numbercond(H_x, ẋ)is larger thanterminate_condthen the path is terminated as too ill-conditioned.parameters::Union{Symbol,TrackerParameters} = :defaultSet theTrackerParametersto control the performance of the path tracking algorithm. The values:default,:conservativeand:fastare shorthands for usingDEFAULT_TRACKER_PARAMETERS,CONSERVATIVE_TRACKER_PARAMETERSresp.FAST_TRACKER_PARAMETERS.
HomotopyContinuation.TrackerParameters — TypeTrackerParametersParameters that control the performance and robustness characteristics of the path tracking algorithm. See [Tim20] for an explanation and derivation of the parameters. We provide three sets of parameters for common use cases:
HomotopyContinuation.DEFAULT_TRACKER_PARAMETERS — ConstantThe default TrackerParameters which have a good balance between robustness and efficiency.
HomotopyContinuation.CONSERVATIVE_TRACKER_PARAMETERS — ConstantTrackerParameters which trade robustness against some speed.
HomotopyContinuation.FAST_TRACKER_PARAMETERS — ConstantTrackerParameters which trade speed against a higher chance of path jumping.
Tracking
HomotopyContinuation.track — Method track(tracker::Tracker, x::AbstractVector, t₁ = 1.0, t₀ = 0.0; debug::Bool = false)Track the given solution x at t₁ using tracker to a solution at t₀.
track(tracker::Tracker, r::TrackerResult, t₁ = 1.0, t₀ = 0.0; debug::Bool = false)Track the solution of the result r from t₁ to t₀.
Result
HomotopyContinuation.TrackerResult — TypeTrackerResultContaining the result of tracking a path with a Tracker.
Fields
return_code::Symbol: A code indicating whether the tracking was successfull (:success). SeeTrackerCodefor all possible values.solution::V: The solution when the tracking stopped.t::ComplexF64: The value oftwhen the tracking stopped.accuracy::Float64: Estimate of the relative accuracy of thesolution.accepted_steps::Int: Number of steps that got accepted.rejected_steps::Int: Number of steps that got rejected.extended_precision::Bool: Indicate whether extended precision is necessary to achieve the accuracy of thesolution.extended_precision_used::Bool: This istrueif during the tracking at any point extended precision was used.
HomotopyContinuation.solution — Methodsolution(result::TrackerResult)Returns the solutions obtained by the Tracker.
HomotopyContinuation.is_success — Methodis_success(result::TrackerResult)Returns true if the path tracking was successfull.
HomotopyContinuation.is_invalid_startvalue — Methodis_invalid_startvalue(result::TrackerResult)Returns true if the path tracking failed since the start value was invalid. You can inspect result.return_code to get the exact return code. Possible values if is_invalid_startvalue(result) == true are
:terminated_invalid_startvalue_singular_jacobianindicates that the Jacobian of the homotopy at the provided start value is singular, i.e., if it has not full-column rank.:terminated_invalid_startvalueindicates that the the provided start value is not sufficiently close to a solution of the homotopy.
HomotopyContinuation.steps — Methodsteps(result::TrackerResult)Returns the number of steps done.
HomotopyContinuation.accepted_steps — Methodaccepted_steps(result::TrackerResult)Returns the number of accepted steps.
HomotopyContinuation.rejected_steps — Methodrejected_steps(result::TrackerResult)Returns the number of rejected_steps steps.
Low-level API
HomotopyContinuation.track! — Methodtrack!(tracker::Tracker, x, t₁ = 1.0, t₀ = 0.0; debug::Bool = false)The same as track but only returns the final TrackerCode.
track!(tracker::Tracker, t₀; debug::Bool = false)Track with tracker the current solution to t₀. This keeps the current state.
HomotopyContinuation.init! — Methodinit!(tracker::Tracker, x₁, t₁, t₀)Setup tracker to track x₁ from t₁ to t₀.
init!(tracker::Tracker, t₀)Setup tracker to continue tracking the current solution to t₀. This keeps the current state.
HomotopyContinuation.TrackerCode — ModuleTrackerCodeThe possible states a CoreTracker can have are of type TrackerCode.codes and can be
TrackerCode.success: Indicates a successfull tracking.TrackerCode.tracking: The tracking is still in progress.TrackerCode.terminated_accuracy_limit: Tracking terminaed since the accuracy was insufficient.TrackerCode.terminated_invalid_startvalue: Tracking terminated since the provided start value was invalid.TrackerCode.terminated_ill_conditioned: Tracking terminated since the path was too ill-conditioned.TrackerCode.terminated_max_steps: Tracking terminated since maximal number of steps is reached.TrackerCode.terminated_step_size_too_small: Trackint terminated since the step size was too small.TrackerCode.terminated_unknown: An unintended error occured. Please consider reporting an issue.
HomotopyContinuation.is_success — Methodis_success(code::TrackerCode.codes)Returns true if code indicates a success in the path tracking.
HomotopyContinuation.is_tracking — Methodis_tracking(code::TrackerCode.codes)Returns true if code indicates that the path tracking is not yet finished.
HomotopyContinuation.is_invalid_startvalue — Methodis_invalid_startvalue(code::TrackerCode.codes)Returns true if code indicates that the path tracking got terminated since the start value was not a regular zero.
HomotopyContinuation.is_terminated — Methodis_terminated(code::TrackerCode.codes)Returns true if code indicates that the path tracking got terminated.