Edit on GitHub

Core Tracker

A CoreTracker is the low-level path tracker. Its job is to track an initial solution x₁ from t₁ to t₀ by following a solution path $x(t)$. For this a predictor-corrector scheme is used. See our introduction guide for a high-level explanation of the predictor corrector scheme

Basic usage

HomotopyContinuation.CoreTracker — Type
CoreTracker

A CoreTracker is the low-level path tracker. Its job is to track an initial solution x₁ from t₁ to t₀ by following a solution path $x(t)$. For this a predictor-corrector scheme is used. See our introduction guide for a high-level explanation of the predictor corrector scheme. The CoreTracker accepts for a value t a solution $x^*$ if $||x(t) - x^*|| < τ$ where $τ$ is controlled by the accuracy option.

To interact with a CoreTracker take a look at track resp. track!. You can also use CoreTracker as an iterator. For this you need to call init!(::CoreTracker, x₁, t₁, t₀) first. There is also iterator if you are only interested in pairs (x,t).

The CoreTracker cannot handle singular solutions or divergent paths. For this you have to use a PathTracker (which uses internally again a CoreTracker).

The CoreTracker can track solutions in projective space if the underlying homotopy is homogeneous and the provided start solution is a projective vector (with type PVector) from the ProjectiveVectors.jl package.

The CoreTracker can also perform a reparamterization of the parameter $t$ from $[0,1]$ towards $[0,∞]$ by $t = e^{-s}$. If the homotopy assumes $t ∈ [0,1]$ this can be done by passing the log_transform = true option. If you already have a homotopy which assumes $s ∈ [0,∞]$ you can use the logarithmic_time_scale = true to tell the core tracker this. In this case the min_step_size criterion is still applied to $t$ and not $s$.

Options

CoreTracker accepts many different options. Here are the options in alphabetic order:

  • accuracy (default 1e-7): The maximal acceptable distance to the true solution at a time step t.
  • auto_scaling (default true): Enables an automatic scaling of the variables by introducing a weighted norm. See also WeightedNorm.
  • initial_step_size: The size of the first step. By default an automatic estimate is computed but this can be overwritten with this option.
  • max_cond (default 1e10): The maximal condition number before a path is terminated due to ill-conditioning. This is only applicable if terminate_ill_conditioned is true.
  • max_corrector_iters (default2`): The maximal number of Newton iteration steps until which the desired accuracy has to be achieved.
  • max_step_size (default Inf): Limit the path tracker to a maximal step size.
  • max_steps (default 1000): The maximal number of steps the path tracker makes. Note that this changes to 10_000 for parameter homotopies.
  • min_step_size (default 1e-14): The path tracking is terminated if the step size is smaller than this value.
  • norm (default InfNorm()): The norm used in the computations. Note that if the auto_scaling is true, this will automatically be converted to a WeightedNorm.
  • patch: It is possible to perform tracking in projective space. For the actual compuations we still need to choose an affine chart. There are multiple charts possible, see AbstractAffinePatch. The default is RandomPatch.
  • precision (default :double): This controls the precision used in the computation of $H(x,t)$. If it is set to :double only double precision arithmetic is used (Complex{Float64}). If it set to :double_double double double arithmetic as implemented by the DoubleFloats package is always used. The option :adaptive changes adaptively the precision.
  • predictor (default Pade21): The predictor used.
  • simple_step_size_alg (default false): By default the step size algorithm presented in arXiv:1902.02968 is used. If this option is true a more simple step size algorithm is used which doubles the step size after 5 consecutive successive steps and halfes the step size after a failed step.
  • terminate_ill_conditioned (default true): Indicates whether the path tracking should be terminated for ill-conditioned paths. A path is considered ill-conditioned if the desirable accuracy is no more achievable or if the condition number of the Jacobian is larger than 1e14.

The easiest way to construct a CoreTracker is to use coretracker and coretracker_startsolutions.

HomotopyContinuation.coretracker_startsolutions — Function
coretracker_startsolutions(args...; kwargs...)

Construct a CoreTracker and startsolutions in the same way solve does it. This also takes the same input arguments as solve. This is convenient if you want to investigate single paths.

HomotopyContinuation.coretracker — Function
coretracker(args...; kwargs...)

Construct a CoreTracker in the same way solve does it. This also takes the same input arguments as solve with the exception that you do not need to specify startsolutions. This is convenient if you want to investigate single paths.

Examples

Obtain single solution

We want to construct a path tracker to track a parametrized system f with parameters p from the parameters a to b.

tracker = coretracker(f; parameters = p, start_parameters = a, target_parameters = b)

You then can obtain a single solution at b by using

x_b = track(tracker, x_a).x

Trace a path

To trace a path you can use the iterator method.

tracker = coretracker(f; parameters = p, start_parameters = a, target_parameters = b)
for (x, t) in iterator(tracker, x₁)
    @show (x,t)
end

If we want to guarantee smooth traces we can limit the maximal step size.

tracker = coretracker(f; parameters = p, max_step_size = 0.01,
                         start_parameters = a, target_parameters = b)
for (x, t) in iterator(tracker, x₁)
    @show (x,t)
end

Result and Status

HomotopyContinuation.CoreTrackerResult — Type
 CoreTrackerResult{V<:AbstractVector}

The result of track(::CoreTracker, x₁, t₁, t₀). You can use is_success to check whether the tracking was successfull and solution to obtain the solution.

Fields

  • returncode The CoreTrackerStatus.states enum.
  • x::V The solution at t.
  • t::ComplexF64 The time t when the path tracker stopped.
  • accuracy::Float64: The estimated accuracy of x.
  • accepted_steps::Int: The number of accepted steps during the tracking.
  • rejected_steps::Int: The number of rejected_steps steps during the tracking.
HomotopyContinuation.CoreTrackerStatus.states — Type
CoreTrackerStatus.states

The possible states a CoreTracker can have are

  • CoreTrackerStatus.success: Indicates a successfull completed tracking
  • CoreTrackerStatus.tracking: The tracking is still in progress
  • CoreTrackerStatus.terminated_maximal_iterations: Tracking terminated since maximal iterations reached.
  • CoreTrackerStatus.terminated_ill_conditioned: Tracking terminated since the path was too ill-conditioned.
  • CoreTrackerStatus.terminated_invalid_startvalue: Tracking terminated since the provided start value was invalid.
  • CoreTrackerStatus.terminated_step_size_too_small
source
HomotopyContinuation.is_terminated — Method
is_terminated(S::CoreTrackerStatus.states)

Returns true if S indicates that the path tracking got terminated. This is not true if is_success(S) is true.

Methods

To track from a start to an endpoint with the CoreTracker we provide the following routines.

HomotopyContinuation.track — Function
track(tracker::CoreTracker, x₁, t₁=1.0, t₀=0.0)::CoreTrackerResult

Track a value x₁ from t₁ to t₀ using the given CoreTracker tracker. This returns a CoreTrackerResult. This modifies tracker. See track! for the possible options. To investigate the behaviour of a particular take a look at path_info.

HomotopyContinuation.track! — Method
track!(tracker::CoreTracker, x₁, t₁=1.0, t₀=0.0)::CoreTrackerStatus.states

Track a value x₁ from t₁ to t₀ using the given CoreTracker tracker. Returns one of the enum values of CoreTrackerStatus indicating the status. Check is_success and is_terminated to test for the status.

If setup_patch is true then init! is called at the beginning of the tracking.

track!(x₀, tracker::CoreTracker, x₁, t₁=1.0, t₀=0.0)::CoreTrackerStatus.states

Additionally also stores the result in x₀ if the tracking was successfull.

HomotopyContinuation.init! — Method
init!(tracker::CT, x₁, t₁, t₀;
  setup_patch::Bool = tracker.options.update_patch,
  loop::Bool = false,
  check_start_value::Bool = !loop)

Setup tracker to track x₁ from t₁ to t₀. Use this if you want to use the tracker as an iterator.

It is also possible to use a CoreTracker as an iterator. This can either be done by the high level iterator method or by directly using a CoreTracker as an iterator. The recommend approach is to simply use iterator.

HomotopyContinuation.iterator — Function
iterator(tracker::CoreTracker, x₁, t₁=1.0, t₀=0.0; affine=true)

Prepare a tracker to make it usable as a (stateful) iterator. Use this if you want to inspect a specific path. In each iteration the tuple (x,t) is returned. If affine == true then x is the affine solution (internally we compute in projective space).

Example

Assume you have CoreTracker tracker and you wan to track x₁ from 1.0 to 0.25:

for (x,t) in iterator(tracker, x₁, 1.0, 0.25)
println("x at t=$t:")
println(x)
end

Note that this is a stateful iterator. You can still introspect the state of the tracker. For example to check whether the tracker was successfull (and did not terminate early due to some problem) you can do

println("Success: ", status(tracker) == CoreTrackerStatus.success)

Introspecting the current state

To introspect the current state we provide the following routines.

LinearAlgebra.cond — Method
LinearAlgebra.cond(tracker::CoreTracker)

Returns the currently computed approximation of the condition number of the Jacobian.

Changing options

To change settings

Deprecated

The following functions are deprecated.