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: Allow the tracker to switch to double-double (≈32 digits) arithmetic where Float64 is not accurate enough: residuals in the Newton corrector, and, if the Float64 Jacobian is too ill-conditioned to be solved accurately, the Jacobian, its LU factorization and the Taylor coefficients of the predictor. Coordinates,tand returned solutions always remainComplexF64. Iffalse, only Float64 arithmetic is used. Extended precision in the Jacobian is only available for systems and homotopies built fromSystem/Homotopy(compiled, interpreted or mixed); customAbstractHomotopys fall back to Float64.extended_precision_stall_steps = 100: A path that is tracked in extended precision can get stuck close to a (numerically) singular point: the steps are accepted, but they are so small that the path makes no progress. If, duringextended_precision_stall_stepsconsecutive accepted steps in extended precision, the remaining distance to the target is reduced by less than the fractionextended_precision_stall_progress, the path is terminated withTrackerCode.terminated_step_size_too_small. Set it to0to disable the check.extended_precision_stall_progress = 1e-8: The minimal fraction of the remaining distance to the target that has to be covered duringextended_precision_stall_stepsconsecutive steps in extended precision, see above.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, in the predictor or in the Newton corrector.
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. This includes the case where the predictor could not compute finite Taylor coefficients, even in extended precision.TrackerCode.terminated_max_steps: Tracking terminated since maximal number of steps is reached.TrackerCode.terminated_step_size_too_small: Tracking terminated since the step size was too small. This includes paths in extended precision that make no progress, see the optionsextended_precision_stall_stepsandextended_precision_stall_progressofTrackerOptions.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.
Extended precision
If the option extended_precision of TrackerOptions is true (the default), the tracker switches to double-double arithmetic (about 32 digits), if iterative refinement with Float64 precision fails. The path coordinates, t and the returned solutions always remain ComplexF64. If the option is false, only Float64 arithmetic is used.
The precision is increased in two stages:
- Newton's method evaluates the residual in double-double, but still solves with the
Float64Jacobian and refines the solution iteratively. - If this refinement does not converge (it stagnates, diverges or gives non-finite values), the Jacobian, its LU factorization and the Taylor coefficients of the predictor are computed in double-double, too. This is called full extended precision. The tracker also enters it if the predictor needs double-double.
In full extended precision, each step additionally checks with a Float64 step whether Float64 suffices again. If so, the tracker leaves full extended precision. Otherwise the path stays in extended precision. init! resets this state for each new path. The memory needed for full extended precision is allocated the first time it is used and reused for all later paths of the same tracker.
The Jacobian and the Taylor coefficients can only be computed in double-double for homotopies built from System or Homotopy (compiled, interpreted or mixed), including parameter homotopies of such systems. For other AbstractHomotopys, only the residual is evaluated in double-double.
Whether extended precision was used on a path can be read off the TrackerResult, see the fields extended_precision and extended_precision_used.
Paths that get stuck in extended precision
Close to a (numerically) singular point a path can get stuck: the steps are accepted, but they are so small, for example 1e-13, that the path hardly advances, and neither extended precision nor smaller steps help. Such a path would only end after max_steps steps. To avoid this, the tracker terminates a path if, during extended_precision_stall_steps (default 100) consecutive accepted steps in extended precision, the remaining distance to the target is reduced by less than the fraction extended_precision_stall_progress (default 1e-8). The tracking code is then TrackerCode.terminated_step_size_too_small. The distance is measured relative to the remaining distance, so that paths approaching a singular endpoint geometrically are not affected. The check is disabled with extended_precision_stall_steps = 0.