Endgame

Endgame

Assume we want to find the all solutions of the polynomial $(x-2)^4$ with homotopy continuation. Then the pathtracker gets into severe trouble near the end of the path since the derivative is $0$ at $x=2$.

How do we solve that problem? The idea is to split the pathtracking into two parts. We first track the path x(t) until the so called endgame zone (starting by default at $t=0.1$). Then we switch to the endgame. The idea is to estimate the value of x(0.0) without tracking the path all the way to $t=0.0$(since this would fail due to a singular Jacobian).

There are two well known endgame strategies. The Power Series Endgame and the Cauchy Endgame. Currently only the Cauchy Endgame is implemented.

At the heart of the endgame routine is the mutable struct Endgamer.

HomotopyContinuation.Endgamer — Type.
Endgamer(endgame_algorithm, pathtracker, [x, R]; kwargs...)

Construct an Endgamer object. The Endgamer 'plays' the endgame with the given endgame_algorithm and uses the given pathtracker to move forward. The endgame is start at x to time R (the endgame radius). In each iteration the endgame moves forward and then performs one iteration of the endgame algorithm. In each iteration we could get another prediction and an estimate of the winding number. Convergence is declared if two consecutive predictions are smaller than a defined tolerance (endgame_abstol).

The following options are available:

  • geometric_series_factor=0.5: The Endgamer moves forward using the geometric series $λ^kR$ where $λ$ is geometric_series_factor.

  • max_winding_number=16 the maximal winding number we allow. If we get a higher winding number

the path is declared failed.

  • endgame_abstol=pathtracker.options.abstol: The tolerance necessary to declare convergence.

Endgamer supports similar to Pathtracker an iterator interface.

source

Examples

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

endgamer = Endgamer(CauchyEndgame(), pathtracker)
endgamer!(endgamer, x, 0.1)
result = EndgamerResult(endgamer)

You can reuse (and should!) resuse an Endgamer for multiple paths

endgamer = Endgamer(CauchyEndgame(), pathtracker))
results = map(xs) do x
  endgame!(endgamer, x, 0.1)
  EndgamerResult(endgamer)
end

Result

HomotopyContinuation.EndgamerResult — Type.
EndgamerResult(endgamer, extended_analysis=false)

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

  • returncode: One of :ill_conditioned_zone, :success, :windingnumber_too_high

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

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

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

  • iterations: The number of iterations the pathtracker needed.

  • npredictions: The number of predictions

  • predictions: All predictions for further introspection (e.g. the path failed)

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

  • windingnumber: The estimated winding number

source

Algorithms

HomotopyContinuation.CauchyEndgame — Type.
CauchyEndgame(;kwargs...)

The main idea of the Cauchy Endgame is to use Cauchy's integral formula to predict the solution of the path $x(t)$, i.e. $x(0)$. At each iteration we are at some point $(x, t)$. We then track the polygon defined by $te^{i2πk/n}$ until we end again at $x$. Here $n$ is the number of samples we take per loop.

The following options are available:

  • samples_per_loop=8: The number of samples we take at one loop.

  • loopclosed_tolerance=1e-5: The tolerance when a loop is considered closed.

  • L=0.75 and $K=0.5$: These are paramters for heuristics. For more details see "A Parallel Endgame " by Bates, Hauenstein and Sommese [1], page 8 and 9.

[1]

Bates, Daniel J., Jonathan D. Hauenstein, and Andrew J. Sommese. "A Parallel Endgame." Contemp. Math 556 (2011): 25-35.

source

Reference

HomotopyContinuation.endgame! — Function.
endgame!(endgamer, x, R)

Play the endgame for x starting from time R.

endgame!(endgamer)

Start the endgamer. You probably want to setup things in prior with setup_endgamer!.

source
HomotopyContinuation.setup_endgamer! — Function.
setup_endgamer!(endgamer, x, R)

Setup endgamer to play the endgame starting from x at time R.

source