PathTracker

# Path Tracker

The `solve` routine is only a very thin wrapper around `PathTracker`. Therefore you can also use `PathTracker` directly. This is for example a good choice if you have to solve the same problem many times.

`` PathTracker{Prob<:AbstractProblem, T, V<:AbstractVector{T}, CT<:CoreTracker}``

`PathTracker` the way to track single paths. It combines the core path tracking routine with an endgame, i.e., it can also deal with singular solutions as well as diverging paths. We call a diverged path a path going to infinity. By convention a path is always tracked from t₁ > 0 towards 0. During the path tracking an approximation of the valuation of a Puiseux series expansion of the solution is computed. This is used to decide whether a path is diverging. To compute singular solutions Cauchy's integral formula is used. There you have to trace out loops around the solution. The number of loops necessary to arrive back at the start point is called the winding number. In order to construct a `PathTracker` it is recommended to use the `pathtracker` and `pathtracker_startsolutions` helper functions. With a `PathTracker` constructed you can track a single path using the `track` method. The result of this will be a `PathResult`.

Keyword arguments

`PathTracker` is a wrapper around `CoreTracker` and thus it is possible to set all options which are available for `CoreTracker`. There are the following `PathTracker` specific options:

General endgame parameters

• `accuracy_eg::Float64=min(accuracy, 1e-5))`: It is possible to change the accuracy during the path tracking. Usually you want lower the accuracy.
• `cond_eg_start::Float64=1e4`: The endgame is only started if the condition of the Jacobian is larger than this threshold.
• `max_winding_number::Int=12`: This limits the maximal number of loops taken in applying Cauchy's formula.
• `min_cond_at_infinity::Float64=1e7`: A path is declared as going to infinity only if it's Jacobian is also larger than this threshold.
• `samples_per_loop::Int=12`: To compute singular solutions Cauchy's integral formula is used. The accuracy of the solutions increases with the number of samples per loop.
• `t_eg_start::Float64=0.1`: The endgame starts only if `t` is smaller than this threshold.
• `tol_val_inf_accurate::Float64=1e-4`: A valuation which would result in a path declared as going to infinity is only accepted if the estimated accuracy of the valuation is less than this threshold.
• `tol_val_finite_accurate::Float64=1e-3`: A valuation which would result in a proper solution is only accepted if the estimated accuracy of the valuation is less than this threshold. This is only affects solutions where the path has at some point near 0 a condition number larger than `cond_eg_start`.

Overdetermined system specific

• `overdetermined_min_accuracy=1e-5`: The minimal accuracy a non-singular solution needs to have to be considered a solution of the original system.
• `overdetermined_min_residual=1e-3`: The minimal residual a singular solution needs to have to be considered a solution of the original system.

The easiest way to construct a `PathTracker`:

``pathtracker_startsolutions(args...; kwargs...)``

Construct a `PathTracker` and start solutions 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.

``pathtracker(args...; kwargs...)``

Construct a `PathTracker` 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.

Examples

Obtain single solution

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

``tracker = pathtracker(f, parameters=p, p₁=a, p₀=b)``

You then can obtain a single solution at `b` by using

``x_b = solution(track(tracker, x_a))``

## Methods

To track a single path you can use the `track` and `track!` methods.

``track(tracker::PathTracker, x₁, t₁::Float64=1.0; path_number::Int=1, details::Symbol=:default, options...)::PathResult``

Track the path with start solution `x₁` from `t₁` towards `t=0`. The `details` options controls the level of details of the informations available in the `PathResult`.

Possible values for the options are

• `accuracy::Float64`
• `max_corrector_iters::Int`
• `max_steps::Int`
• `start_parameters::AbstractVector`
• `target_parameters::AbstractVector`
``track!(tracker::PathTracker, x₁, t₁::Float64=1.0; options...)::PathTrackerStatus.states``

Track the path with start solution `x₁` from `t₁` towards `t=0`.

Possible values for the options are

• `accuracy::Float64`
• `max_corrector_iters::Int`
• `max_steps::Int`
• `start_parameters::AbstractVector`
• `target_parameters::AbstractVector`

The return type of `track!` is

``PathTrackerStatus.states``

The possible return codes the path tracker can return are

• `PathTrackerStatus.success`
• `PathTrackerStatus.at_infinity`
• `PathTrackerStatus.terminated_maximal_iterations`
• `PathTrackerStatus.terminated_invalid_startvalue`
• `PathTrackerStatus.terminated_step_size_too_small`
• `PathTrackerStatus.terminated_singularity`
• `PathTrackerStatus.terminated_ill_conditioned`
• `PathTrackerStatus.terminated`
• `PathTrackerStatus.post_check_failed`
• `PathTrackerStatus.excess_solution`
source

In the case that you track paths of parameter homotopy you can also change the parameters using

``set_parameters!(tracker::PathTracker; start_parameters=nothing, target_parameters=nothing)``

Set the parameters of a parameter homotopy.

## PathResult

For each path we return a `PathResult` containing the detailed information about the single path.

``PathResult{V<:AbstractVector}``

A `PathResult` is the result of tracking of a path using `PathTracker`. Its fields are

• `return_code`: One of `:success`, `:at_infinity` or any error code in `PathTrackerStatus.states` converted to a `Symbol`.

• `solution::V`: The solution vector.

• `t::Float64`: The value of `t` at which `solution` was computed. Note that if `return_code` is `:at_infinity`, then `t` is the value when this was decided.

• `accuracy::Union{Nothing, Float64}`: An approximation of \$||x-x^*||₂\$ where \$x\$ is the computed solution and \$x^*\$ is the true solution.

• `residual::Union{Nothing, Float64}`: The value of the 2-norm of `H(solution, 0)`.

• `multiplicity::Union{Nothing, Int}` is the multiplicity of the `solution`. This is only assigned by. `singular`.

• `condition_jacobian::Union{Nothing, Float64}`: This is the condition number of the row-equilibrated Jacobian at the solution. A high condition number indicates a singularity.

• `winding_number:Union{Nothing, Int}`: The estimated winding number. This is a lower bound on the multiplicity of the solution.

• `start_solution::Union{Nothing, Int}`: The start solution of the path.

• `accepted_steps::Int`: The number of accepted steps during the path tracking.

• `rejected_steps::Int`: The number of rejected steps during the path tracking.

• `valuation::Union{Nothing, Vector{Float64}}`: An approximation of the valuation of the Puiseux series expansion of `x(t)`.

• `valuation_accuracy::Union{Nothing, Vector{Float64}}`: An estimate of the accuracy of the valuation of the Puiseux series expansion of `x(t)`.

PathResult(tracker::PathTracker, startsolution=nothing, pathnumber::Union{Nothing,Int}=nothing; details=:default)

Possible `details` values are `:minimal` (minimal details), `:default` (default) and `:extensive` (all information possible).

The following helper functions are provided

``solution(pathresult)``

Get the solution of the path.

``accuracy(pathresult)``

Get the accuracy of the solution \$x\$ of the path, i.e., \$||H(x, 0)||₂\$.

``multiplicity(P::PathResult{T})``

Returns the multiplicity of `P`.

``residual(pathresult)``

Get the residual of the solution \$x\$ of the path, i.e., \$||H(x, 0)||₂\$.

``start_solution(pathresult)``

Get the start solution of the solution \$x\$ of the path.

``is_real(pathresult; tol=1e-6)``

We consider a result as `real` if the 2-norm of the imaginary part of the solution is at most `tol`.

``is_success(pathresult)``

Checks whether the path is successfull.

``is_failed(pathresult)``

Checks whether the path failed.

``is_affine(pathresult)``

Return`s true if the solution is an affine vector.

``is_projective(pathresult)``

Return`s true if the solution is a projective vector.

``is_at_infinity(pathresult)``

Checks whether the path goes to infinity.

``is_singular(pathresult; tol=1e10)``

Checks whether the path result is singular. This is true if the multiplicity is larger than 1 or if the condition number of the Jacobian is larger than `tol`.

``is_nonsingular(pathresult; tol=1e10)``

Checks whether the path result is non-singular. This is true if it is not singular.