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 — Type
Tracker(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: 4
source
HomotopyContinuation.TrackerOptions — Type
TrackerOptions(; options...)

The set of options for a Tracker.

Options

  • automatic_differentiation = 1: The value automatic_differentiation determines 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 use automatic_differentiation = 3.
  • max_steps = 10_000: The maximal number of steps a tracker attempts
  • max_step_size = Inf: The maximal size of a step
  • max_initial_step_size = Inf: The maximal size of the first step
  • min_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, t and returned solutions always remain ComplexF64. If false, only Float64 arithmetic is used. Extended precision in the Jacobian is only available for systems and homotopies built from System/Homotopy (compiled, interpreted or mixed); custom AbstractHomotopys 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, during extended_precision_stall_steps consecutive accepted steps in extended precision, the remaining distance to the target is reduced by less than the fraction extended_precision_stall_progress, the path is terminated with TrackerCode.terminated_step_size_too_small. Set it to 0 to disable the check.
  • extended_precision_stall_progress = 1e-8: The minimal fraction of the remaining distance to the target that has to be covered during extended_precision_stall_steps consecutive steps in extended precision, see above.
  • terminate_cond = 1e13: If the relative component-wise condition number cond(H_x, ẋ) is larger than terminate_cond then the path is terminated as too ill-conditioned.
  • parameters::Union{Symbol,TrackerParameters} = :default Set the TrackerParameters to control the performance of the path tracking algorithm. The values :default, :conservative and :fast are shorthands for using DEFAULT_TRACKER_PARAMETERS, CONSERVATIVE_TRACKER_PARAMETERS resp. FAST_TRACKER_PARAMETERS.
source

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₀.

source

Result

HomotopyContinuation.TrackerResult — Type
TrackerResult

Containing the result of tracking a path with a Tracker.

Fields

  • return_code::Symbol: A code indicating whether the tracking was successfull (:success). See TrackerCode for all possible values.
  • solution::V: The solution when the tracking stopped.
  • t::ComplexF64: The value of t when the tracking stopped.
  • accuracy::Float64: Estimate of the relative accuracy of the solution.
  • 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 the solution.
  • extended_precision_used::Bool: This is true if during the tracking at any point extended precision was used, in the predictor or in the Newton corrector.
source
HomotopyContinuation.is_invalid_startvalue — Method
is_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_jacobian indicates that the Jacobian of the homotopy at the provided start value is singular, i.e., if it has not full-column rank.
  • :terminated_invalid_startvalue indicates that the the provided start value is not sufficiently close to a solution of the homotopy.
source

Low-level API

HomotopyContinuation.track! — Method
track!(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.

source
HomotopyContinuation.init! — Method
init!(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.

source
HomotopyContinuation.TrackerCode — Module
TrackerCode

The 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 options extended_precision_stall_steps and extended_precision_stall_progress of TrackerOptions.
  • TrackerCode.terminated_unknown: An unintended error occured. Please consider reporting an issue.
source

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:

  1. Newton's method evaluates the residual in double-double, but still solves with the Float64 Jacobian and refines the solution iteratively.
  2. 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.

  • Tim20Timme, S. "Mixed Precision Path Tracking for Polynomial Homotopy Continuation". arXiv:1902.02968 (2020)
  • Tim20Timme, S. "Mixed Precision Path Tracking for Polynomial Homotopy Continuation". arXiv:1902.02968 (2020)