Macaulay2 » Documentation
Packages » NumericalAlgebraicGeometry :: track(List,List,List)
next | previous | forward | backward | up | index | toc

# track(List,List,List) -- track a linear segment homotopy given start and target system

- Function: track
- Usage:
    `solsT = track(S,T,solsS)`
- Inputs:
  - S, a list, contains the polynomials in the start system
  - T, a list, contains the polynomials in the target system
  - solsS, a list, contains start solutions
- Optional inputs:
  - AffinePatches => ..., default value null, reserved for developers
  - CorrectorTolerance => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - EndZoneFactor => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - gamma => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - InfinityThreshold => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - maxCorrSteps => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - MultistepDegree => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - NoOutput => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - Normalize => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - numberSuccessesBeforeIncrease => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - Predictor => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - Projectivize => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - SingularConditionNumber => ..., default value null, set/get the default parameters for continuation algorithms
  - SLP => ..., default value null, reserved for developers
  - SLPcorrector => ..., default value null, reserved for developers
  - SLPpredictor => ..., default value null, reserved for developers
  - Software => ..., default value null, specify internal or external software
  - stepIncreaseFactor => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - tDegree => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - tStep => ..., default value null, options for core functions of Numerical Algebraic Geometry
  - tStepMin => ..., default value null, options for core functions of Numerical Algebraic Geometry
- 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. For an introduction to the subject see

- A.J. Sommese, J. Verschelde, and C.W. Wampler, "Introduction to numerical algebraic geometry", in "Solving polynomial equations" (2005), 301--338
- A.J. Sommese and C.W. Wampler, "The numerical solution of systems of polynomials", World Scientific Publishing (2005)

The package implements a most commonly used homotopy:

H(t) = \gamma t^d T + (1-t)^d S

where S and T are square systems (number of equations = number of variables) of polynomials over CC, 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 = {{-4.40616e-16, -1}, {1, 1.22819e-15}, {4.40616e-16, 1}, {-1,
         ------------------------------------------------------------------------
         -1.22819e-15}}

    o5 : List

Another outcome of tracking a path is divergence (established heuristically). In that case the divergent paths are marked with an I (status is set to 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 = {[M,t=.999998], {.707107, .707107}, [M,t=.999998], {-.707107,
          -----------------------------------------------------------------------
          -.707107}}

    o10 : List

Some divergent paths as well as most of the paths ending in singular (multiplicity>1) or near-singular (clustered) solutions are marked with an M (status is set to MinStepFailure).

    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 C. Beltran and A. Leykin, "Certified numerical homotopy tracking", Experimental Mathematics 21(1): 69-83 (2012)):

    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 = {{.00000107266, -.70712, .70712}, {.707125, -1.48993e-7, .707107},
          -----------------------------------------------------------------------
          {-.00000107266, .70712, .70712}, {-.707125, 1.48993e-7, .707107}}

    o20 : List

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

## Caveat

Predictor=>Certified works only with (Software=>M2 or Software=>M2engine) and Normalize=>true.

Unspecified optional arguments (with default values null) have their actual values taken from a local hashtable of defaults controlled by the functions getDefault and setDefault.

## See also

- solveSystem -- solve a system of polynomial equations
- setDefault -- set/get the default parameters for continuation algorithms
- Point -- a type used to store a point in complex space

## Ways to use this method:

- track(List,List,List) -- track a linear segment homotopy given start and target system
- `track(PolySystem,PolySystem,List)`

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/NumericalAlgebraicGeometry/doc.m2:290:0.