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

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

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.

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.

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.
  • 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.
  • 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)