# 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`

.

`HomotopyContinuation.TrackerParameters`

— Type`TrackerParameters`

Parameters 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`

— Constant`TrackerParameters`

which trade robustness against some speed.

`HomotopyContinuation.FAST_TRACKER_PARAMETERS`

— Constant`TrackerParameters`

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`

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

`HomotopyContinuation.solution`

— Method`solution(result::TrackerResult)`

Returns the solutions obtained by the `Tracker`

.

`HomotopyContinuation.is_success`

— Method`is_success(result::TrackerResult)`

Returns `true`

if the path tracking was successfull.

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

`HomotopyContinuation.steps`

— Method`steps(result::TrackerResult)`

Returns the number of steps done.

`HomotopyContinuation.accepted_steps`

— Method`accepted_steps(result::TrackerResult)`

Returns the number of accepted steps.

`HomotopyContinuation.rejected_steps`

— Method`rejected_steps(result::TrackerResult)`

Returns the number of rejected_steps steps.

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

`HomotopyContinuation.is_success`

— Method`is_success(code::TrackerCode.codes)`

Returns `true`

if `code`

indicates a success in the path tracking.

`HomotopyContinuation.is_tracking`

— Method`is_tracking(code::TrackerCode.codes)`

Returns `true`

if `code`

indicates that the path tracking is not yet finished.

`HomotopyContinuation.is_invalid_startvalue`

— Method`is_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`

— Method`is_terminated(code::TrackerCode.codes)`

Returns `true`

if `code`

indicates that the path tracking got terminated.