track(List,List,List) -- track a user homotopy

Synopsis

Usage:
solsT = track(S,T,solsS)
Function: track
Inputs:
- S, a list, List of polynomials in the start system
- T, a list, List of polynomials in the target system
- solsS, a list, List of start solutions
Optional inputs:
- gamma => default value null, a parameter in the homotopy: H(t)=(1-t)^tDegree S + gamma t^tDegree T
- tDegree => default value null, a parameter in the homotopy: H(t)=(1-t)^tDegree S + gamma t^tDegree T
- tStep => default value null, initial step size
- tStepMin => default value null, minimal step size
- stepIncreaseFactor => default value null, determine how step size is adjusted
- numberSuccessesBeforeIncrease => default value null, determine how step size is adjusted
- Predictor => default value null, a method to predict the next point on the homotopy path: choose between RungeKutta4, Tangent, Euler, Secant, Multistep, Certified. The option Certified provides certified tracking.
- MultistepDegree => default value null, degree of the Multistep predictor
- maxCorrSteps => default value null, max number of steps corrector takes before a failure is declared
- CorrectorTolerance => default value null, corrector succeeds if the relative error does not exceed this tolerance
- EndZoneFactor => default value null, size of `end zone'
- InfinityThreshold => default value null, paths are truncated if the norm of the approximation exceeds the threshold
- Projectivize => default value null, if true then the system is homogenized and projective tracker is executed
- Normalize => default value null, normalize the start and target systems w.r.t. Bombieri-Weyl norm
- NoOutput => default value null, if true, no output is produced (useful in combination with getSolution (missing documentation))
- AffinePatches => ..., -- track a user homotopy
- SLP => ..., -- track a user homotopy
- SLPcorrector => ..., -- track a user homotopy
- SLPpredictor => ..., -- track a user homotopy
- Software => ..., -- specify internal or external software
Outputs:
- a list, solsT is a list of Points that are solutions of T=0 obtained by continuing solsS of S=0

Description

Polynomial homotopy continuation techniques are used to obtain solutions of the target system given a start system. Most commonly the following homotopy is considered:
H(t) = gamma t^d T + (1-t)^d S
where t is in the interval [0,1] and d = tDegree. Here is an example with regular solutions at the ends of all homotopy paths:

i1 : R = CC[x,y];

i2 : S = {x^2-1,y^2-1};

i3 : T = {x^2+y^2-1, x*y};

i4 : solsS = {(1,-1),(1,1),(-1,1),(-1,-1)};

i5 : track(S,T,solsS)  

o5 = {{-3.8337e-16, -1}, {1, 1.17962e-15}, {3.8337e-16, 1}, {-1,
     ------------------------------------------------------------------------
     -1.17962e-15}}

o5 : List

Another outcome of tracking a path is divergence (established heuristically). In that case the divergent paths are marked with I for infinity:

i6 : R = CC[x,y];

i7 : S = {x^2-1,y^2-1};

i8 : T = {x^2+y^2-1, x-y};

i9 : solsS = {(1,-1),(1,1),(-1,1),(-1,-1)};

i10 : track(S,T,solsS,gamma=>0.6+0.8*ii) 

o10 = {[I,t=.999988], {.707107, .707107}, [I,t=.999988], {-.707107,
      -----------------------------------------------------------------------
      -.707107}}

o10 : List

Some divergent paths as well as most of the paths ending in singular (solutions with multiplicity>1) or near-singular (clustered solutions) are indicated by M for "minimal step" failure:

i11 : R = CC[x,y];

i12 : S = {x^2-1,y^2-1};

i13 : T = {x^2+y^2-1, (x-y)^2};

i14 : solsS = {(1,-1),(1,1),(-1,1),(-1,-1)};

i15 : track(S,T,solsS) 

o15 = {[M,t=.999998], [M,t=.999998], [M,t=.999998], [M,t=.999998]}

o15 : List

Tracking in the projective space uses the homotopy corresponding to an arc of a great circle on a unit sphere in the space of homogeneous polynomial systems of a fixed degree. In particular, this is done for certified homotopy tracking (see Beltran, Leykin "Certified numerical homotopy tracking"):

i16 : R = CC[x,y,z];

i17 : S = {x^2-z^2,y^2-z^2};

i18 : T = {x^2+y^2-z^2, x*y};

i19 : solsS = {(1,-1,1),(1,1,1),(-1,1,1),(-1,-1,1)};

i20 : track(S,T,solsS,Predictor=>Certified,Normalize=>true)

o20 = {{.00000207617, -.706804, .70744}, {.707138, -.0017439, .707107},
      -----------------------------------------------------------------------
      {-.00000207617, .706804, .70744}, {-.707138, .0017439, .707107}}

o20 : List

Note that projective tracker is invoked either if the target system is a homogenous system or if Projectivize=>true is specified.

Caveat

Predictor=>Certified works only with Software=>[M2,M2engine] and Normalize=>true

track(List,List,List) -- track a user homotopy

Synopsis

Description

Caveat

See also