Pathtracking

Pathtracking routines

Pathtracking is at the core of each homotopy continuation method. It is the routine to track a given homotopy $H(x, t)$ from a start value $x_1$ at time $t_1$ to a target value $x_0$ at time $t_0$.

At the heart of the pathtracking routine is the mutable struct Pathtracker.

HomotopyContinuation.Pathtracker — Type.
Pathtracker(H::AbstractHomotopy{T}, alg, [HT::Type=widen(T)]; kwargs...)

Construct a Pathtracker object. This contains all informations to track a single path for H with the given pathtracking algorithm alg. The optional type HT is used if the pathracker decides to switch to a high precision mode.

The following keyword arguments are supported:

  • path_precision=1e-6: The precision for which a correction step is decleared successfull.

  • corrector_maxiters=3: The maximal number of correction iterations. A higher value as 3 is not recommended.

  • initial_steplength=0.1: The initial steplength a preditor-corrector algorithm uses.

  • consecutive_successfull_steps_until_steplength_increase=3: The number of consecutive successfull steps until the step length is increased multiplied with the factor steplength_increase_factor.

  • steplength_increase_factor=2.0

  • steplength_decrease_factor=inv(steplength_increase_factor): If a correction step fails the step length is multiplied with this factor.

  • maxiters=10_000: The maximum number of iterations.

  • vebose=false: Print additional informations / warnings during the computation.

source

Examples

The follwing example demonstrates the usual workflow. You first create a Pathtracker object, then you can track a path from a given start value and finally you create a PathtrackerResult.

pathtracker = Pathtracker(H, SphericalPredictorCorrector())
track!(pathtracker, x, 1.0, 0.0)
result = PathtrackerResult(pathtracker)

You can reuse (and should!) resuse a Pathtracker for multiple paths

pathtracker = Pathtracker(H, SphericalPredictorCorrector())
results = map(xs) do x
  track!(pathtracker, x, 1.0, 0.0)
  PathtrackerResult(pathtracker)
end

Pathtracker also supports the iterator interface. This returns the complete Pathtracker object at each iteration. This enables all sort of nice features. For example you could store the actual path the pathtracker takes:

pathtracker = Pathtracker(H, SphericalPredictorCorrector())
setup_pathtracker!(pathtracker, x, 1.0, 0.0)
path = []
for t in pathtracker
  push!(path, current_value(t))
end

Result

See also here.

HomotopyContinuation.PathtrackerResult — Type.
PathtrackerResult(pathtracker, extended_analysis=false)

Reads the result from the current pathtracker state. A PathtrackerResult contains:

  • returncode: One of :max_iterations, :singularity, :invalid_startvalue, :success.

  • solution::Vector{T}: The solution.

  • residual::Float64: The value of the infinity norm of H(solution, 0).

  • iterations: The number of iterations the pathtracker needed.

  • angle_to_infinity: The angle to infinity is the angle of the solution to the hyperplane where the homogenizing coordinate is $0$.

If extended_analysis=true there is also:

  • newton_residual: The value of the 2-norm of $J_H(\text{solution})^{-1}H(\text{solution}, 0)$

  • condition_number: A high condition number indicates singularty. See Homotopies.κ for details.

source

Algorithms

Currently, the following pathtracking routines are implemented

HomotopyContinuation.SphericalPredictorCorrector — Type.
SphericalPredictorCorrector

This algorithm uses as an prediction step an explicit Euler method. For the prediction and correction step the Jacobian is augmented by Hermitian transposed $x^*$ to get a square system. Therefore the prediciton step looks like

\[x_{k+1} = x_k - Δt\begin{bmatrix} J_H(x, t) \\ x^* \end{bmatrix}^{-1} \frac{∂H}{∂t}(x, t)\]

and the correction step looks like

\[x_{k+1} = x_{k+1} - \begin{bmatrix} J_H(x, t) \\ x^* \end{bmatrix}^{-1} H(x, t)\]

After each prediciton and correction the algorithm normalizes $x$ again, i.e. $x$ is then a point on the sphere again.

This algorithm tracks the path in the projective space.

source
HomotopyContinuation.AffinePredictorCorrector — Type.
AffinePredictorCorrector

This algorithm uses as an prediction step an explicit Euler method. Therefore the prediciton step looks like

\[x_{k+1} = x_k - ΔtJ_H(x, t)^{-1}\frac{∂H}{∂t}(x, t)\]

and the correction step looks like

\[x_{k+1} = x_{k+1} - J_H(x, t)^{-1}H(x, t)\]

This algorithm tracks the path in the affine space.

source

Reference

HomotopyContinuation.track! — Function.
track!(pathtracker, x0, s_start, s_target)

Track a startvalue x0 from s_start to s_target using the given pathtracker.

track!(pathtracker)

Run the given pathtracker. You can use this in combination with setup_pathtracker!.

source
HomotopyContinuation.setup_pathtracker! — Function.
setup_pathtracker!(tracker, x0, s_start, s_end)

Reset the given pathtracker tracker and set it up to track x0 form s_start to s_end.

source
HomotopyContinuation.current_value — Function.
current_value(pathtracker)

Get the current value of the pathtracker.

source