Macaulay2 » Documentation
Packages » NumericalAlgebraicGeometry :: NumericalAlgebraicGeometry
next | previous | forward | backward | up | index | toc

# NumericalAlgebraicGeometry -- Numerical Algebraic Geometry

## Description

The package NumericalAlgebraicGeometry, also known as NAG4M2 (Numerical Algebraic Geometry for Macaulay2), implements methods of polynomial homotopy continuation to solve systems of polynomial equations,

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

    i2 : F = {x^2+y^2+z^2-1, y-x^2, z-x^3};

    i3 : s = solveSystem F

    o3 = {{.540536+1.03152*ii, -.771845+1.11514*ii, -1.5675-.193395*ii},
         ------------------------------------------------------------------------
         {-.737353, .543689, -.400891}, {-.540536-1.03152*ii,
         ------------------------------------------------------------------------
         -.771845+1.11514*ii, 1.5675+.193395*ii}, {-.540536+1.03152*ii,
         ------------------------------------------------------------------------
         -.771845-1.11514*ii, 1.5675-.193395*ii}, {.737353, .543689, .400891},
         ------------------------------------------------------------------------
         {.540536-1.03152*ii, -.771845-1.11514*ii, -1.5675+.193395*ii}}

    o3 : List

    i4 : realPoints s

    o4 = {{-.737353, .543689, -.400891}, {.737353, .543689, .400891}}

    o4 : List

and describe positive-dimensional complex algebraic varieties,

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

    i6 : sph = x^2+y^2+z^2-1;

    i7 : I = ideal {x*sph*(y-x^2), sph*(z-x^3)};

    o7 : Ideal of R

    i8 : numericalIrreducibleDecomposition I

    o8 = a "numerical variety" with components in
         dim 1:  (dim=1,deg=1) (dim=1,deg=3)
         dim 2:  (dim=2,deg=2)

    o8 : NumericalVariety

Basic types (such as Point and WitnessSet) are defined in the package NAGtypes.

### Basic functions:

- track -- track a linear segment homotopy given start and target system
- solveSystem -- solve a system of polynomial equations
- refine -- refine numerical solutions to a system of polynomial equations
- totalDegreeStartSystem -- construct a start system for the total degree homotopy
- numericalIrreducibleDecomposition -- constructs a numerical variety defined by the given ideal
- sample -- sample a point on a component
- isSubset(NumericalVariety,NumericalVariety)

Optionally, the user may outsource some basic routines to Bertini and PHCpack (look for Software option).

### Service functions:

- Many service functions (such as areEqual and sortSolutions) are defined in the package NAGtypes.
- setDefault -- set/get the default parameters for continuation algorithms
- getDefault -- set/get the default parameters for continuation algorithms
- NAGtrace -- set the trace level in NumericalAlgebraicGeometry package
- newton -- Newton-Raphson method
- isOn -- determines if a point belongs to a variety
- union -- compute the union
- removeRedundantComponents -- remove redundant components

### Functions related to Certified tracking:

- randomInitialPair -- a random initial pair
- goodInitialPair -- make an initial pair conjectured to be good by Shub and Smale
- randomSd -- a random homogeneous system of polynomial equations

### References:

- 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)
- C. Beltran and A. Leykin, "Certified numerical homotopy tracking", Experimental Mathematics 21(1): 69-83 (2012)
- R. Krone and A. Leykin, "Numerical algorithms for detecting embedded components.", arXiv:1405.7871

## Authors

- Anton Leykin <leykin@math.gatech.edu>
- Robert Krone <krone@math.gatech.edu>

## Certification

Version 1.4 of this package was accepted for publication in volume 3 of The Journal of Software for Algebra and Geometry: Macaulay2 on 2011-05-20, in the article Numerical Algebraic Geometry (DOI: 10.2140/jsag.2011.3.5). That version can be obtained from the journal.

## Version

This documentation describes version 1.24 of NumericalAlgebraicGeometry, released May 2024.

## Citation

If you have used this package in your research, please cite it as follows:

    @misc{NumericalAlgebraicGeometrySource,
      title = {{NumericalAlgebraicGeometry: A \emph{Macaulay2} package. Version~1.24}},
      author = {Anton Leykin and Robert Krone},
      howpublished = {A \emph{Macaulay2} package available at
        "http://people.math.gatech.edu/~aleykin3/NAG4M2"}
    }

    @article{NumericalAlgebraicGeometryArticle,
      title = {{Numerical Algebraic Geometry}},
      author = {Anton Leykin and Robert Krone},
      journal = {The Journal of Software for Algebra and Geometry: Macaulay2},
      volume = {3},
      year = {2011},
    }

## Exports

- Types
  - `GateHomotopy` -- see gateHomotopy(GateMatrix,GateMatrix,InputGate) -- homotopy implemented via straight line programs
  - GateParameterHomotopy -- a homotopy that involves parameters and is implemented via straight line programs
  - GateSystem -- a system of functions evaluated via a straightline program
  - Homotopy -- a homotopy abstract type
  - ParameterHomotopy -- a homotopy that involves parameters
  - SpecializedParameterHomotopy -- a homotopy obtained from a parameter homotopy by specializing parameters
- Functions and commands
  - deflate -- first-order deflation
  - `deflateAndStoreDeflationSequence` -- see deflate -- first-order deflation
  - `liftPointToDeflation` -- see deflate -- first-order deflation
  - endGameCauchy -- Cauchy end game for getting a better approximation of a singular solution
  - evaluateH -- evaluates the homotopy
  - evaluateHt -- evaluates the derivative of the homotopy with respect to the continuation parameter
  - evaluateHx -- evaluates the jacobian of the homotopy
  - `gateHomotopy` -- see gateHomotopy(GateMatrix,GateMatrix,InputGate) -- homotopy implemented via straight line programs
  - gateSystem -- a constructor for GateSystem
  - `goodInitialPair` -- see goodInitialPair(List) -- make an initial pair conjectured to be good by Shub and Smale
  - isOn -- determines if a point belongs to a variety
  - `isSolution` -- see isSolution(AbstractPoint,PolySystem) -- check if a point satisfies a polynomial system approximately
  - `NAGtrace` -- see NAGtrace(ZZ) -- set the trace level in NumericalAlgebraicGeometry package
  - newton -- Newton-Raphson method
  - `hypersurfaceSection` -- see numericalIntersection -- intersection of numerical varieties
  - numericalIntersection -- intersection of numerical varieties
  - `numericalIrreducibleDecomposition` -- see numericalIrreducibleDecomposition(Ideal) -- constructs a numerical variety defined by the given ideal
  - `parameterHomotopy` -- see parameterHomotopy(List,List,List) -- solve a parametric system of equations
  - parametricSegmentHomotopy -- creates an ansatz for a segment homotopy
  - randomInitialPair -- a random initial pair
  - `randomSd` -- see randomSd(List) -- a random homogeneous system of polynomial equations
  - `refine` -- see refine(List,List) -- refine numerical solutions to a system of polynomial equations
  - `regeneration` -- see regeneration(List) -- solve a system of polynomial equations with regeneration method
  - `removeRedundantComponents` -- see removeRedundantComponents(NumericalVariety) -- remove redundant components
  - `sample` -- see sample(WitnessSet) -- sample a point on a component
  - segmentHomotopy -- a segment homotopy
  - `getDefault` -- see setDefault -- set/get the default parameters for continuation algorithms
  - setDefault -- set/get the default parameters for continuation algorithms
  - `solveGenericSystemInTorus` -- see solveGenericSystemInTorus(List) -- solve a generic system of sparse polynomial equations in the torus
  - `solveSystem` -- see solveSystem(List) -- solve a system of polynomial equations
  - `specialize` -- see specialize(ParameterHomotopy,Matrix) -- specialize a parameter homotopy
  - squareUp -- square up a polynomial system
  - `totalDegreeStartSystem` -- see totalDegreeStartSystem(List) -- construct a start system for the total degree homotopy
  - `track` -- see track(List,List,List) -- track a linear segment homotopy given start and target system
  - `trackHomotopy` -- see trackHomotopy(Homotopy,List) -- follow points along a homotopy
- Methods
  - decompose(WitnessSet) -- decompose a witness set into irreducibles
  - `deflate(Ideal)` -- see deflate -- first-order deflation
  - `deflate(PolySystem,AbstractPoint)` -- see deflate -- first-order deflation
  - `deflate(PolySystem,List)` -- see deflate -- first-order deflation
  - `deflate(PolySystem,Matrix)` -- see deflate -- first-order deflation
  - `deflate(PolySystem,Sequence)` -- see deflate -- first-order deflation
  - `deflate(PolySystem,ZZ)` -- see deflate -- first-order deflation
  - `deflateAndStoreDeflationSequence(AbstractPoint,PolySystem)` -- see deflate -- first-order deflation
  - `liftPointToDeflation(AbstractPoint,PolySystem,ZZ)` -- see deflate -- first-order deflation
  - `endGameCauchy(GateHomotopy,Number,AbstractPoint)` -- see endGameCauchy -- Cauchy end game for getting a better approximation of a singular solution
  - `endGameCauchy(GateHomotopy,Number,MutableMatrix)` -- see endGameCauchy -- Cauchy end game for getting a better approximation of a singular solution
  - `evaluateH(GateHomotopy,Matrix,Number)` -- see evaluateH -- evaluates the homotopy
  - `evaluateH(Homotopy,Matrix,Number)` -- see evaluateH -- evaluates the homotopy
  - `evaluateH(ParameterHomotopy,Matrix,Matrix,Number)` -- see evaluateH -- evaluates the homotopy
  - `evaluateH(SpecializedParameterHomotopy,Matrix,Number)` -- see evaluateH -- evaluates the homotopy
  - evaluateH(GateParameterHomotopy,Matrix,Matrix,Number) -- evaluate (gate) parameter homotopy and its derivatives
  - `evaluateHt(GateParameterHomotopy,Matrix,Matrix,Number)` -- see evaluateH(GateParameterHomotopy,Matrix,Matrix,Number) -- evaluate (gate) parameter homotopy and its derivatives
  - `evaluateHx(GateParameterHomotopy,Matrix,Matrix,Number)` -- see evaluateH(GateParameterHomotopy,Matrix,Matrix,Number) -- evaluate (gate) parameter homotopy and its derivatives
  - `evaluateHt(GateHomotopy,Matrix,Number)` -- see evaluateHt -- evaluates the derivative of the homotopy with respect to the continuation parameter
  - `evaluateHt(Homotopy,Matrix,Number)` -- see evaluateHt -- evaluates the derivative of the homotopy with respect to the continuation parameter
  - `evaluateHt(ParameterHomotopy,Matrix,Matrix,Number)` -- see evaluateHt -- evaluates the derivative of the homotopy with respect to the continuation parameter
  - `evaluateHt(SpecializedParameterHomotopy,Matrix,Number)` -- see evaluateHt -- evaluates the derivative of the homotopy with respect to the continuation parameter
  - `evaluateHx(GateHomotopy,Matrix,Number)` -- see evaluateHx -- evaluates the jacobian of the homotopy
  - `evaluateHx(Homotopy,Matrix,Number)` -- see evaluateHx -- evaluates the jacobian of the homotopy
  - `evaluateHx(ParameterHomotopy,Matrix,Matrix,Number)` -- see evaluateHx -- evaluates the jacobian of the homotopy
  - `evaluateHx(SpecializedParameterHomotopy,Matrix,Number)` -- see evaluateHx -- evaluates the jacobian of the homotopy
  - gateHomotopy(GateMatrix,GateMatrix,InputGate) -- homotopy implemented via straight line programs
  - `numVariables(GateHomotopy)` -- see gateHomotopy(GateMatrix,GateMatrix,InputGate) -- homotopy implemented via straight line programs
  - gateMatrix(GateSystem) -- evaluation circuit used for the system
  - `evaluate(GateSystem,Matrix,Matrix)` -- see GateSystem -- a system of functions evaluated via a straightline program
  - `net(GateSystem)` -- see GateSystem -- a system of functions evaluated via a straightline program
  - `numFunctions(GateSystem)` -- see GateSystem -- a system of functions evaluated via a straightline program
  - `numParameters(GateSystem)` -- see GateSystem -- a system of functions evaluated via a straightline program
  - `numVariables(GateSystem)` -- see GateSystem -- a system of functions evaluated via a straightline program
  - `gateSystem(BasicList,BasicList,GateMatrix)` -- see gateSystem -- a constructor for GateSystem
  - `gateSystem(GateMatrix,GateMatrix)` -- see gateSystem -- a constructor for GateSystem
  - `gateSystem(GateMatrix,GateMatrix,GateMatrix)` -- see gateSystem -- a constructor for GateSystem
  - `gateSystem(Matrix)` -- see gateSystem -- a constructor for GateSystem
  - `gateSystem(PolySystem)` -- see gateSystem -- a constructor for GateSystem
  - `gateSystem(PolySystem,List)` -- see gateSystem -- a constructor for GateSystem
  - GateSystem ^ List -- a subsystem with specified equations
  - goodInitialPair(List) -- make an initial pair conjectured to be good by Shub and Smale
  - `isOn(AbstractPoint,Ideal)` -- see isOn -- determines if a point belongs to a variety
  - `isOn(AbstractPoint,NumericalVariety)` -- see isOn -- determines if a point belongs to a variety
  - `isOn(AbstractPoint,RingElement)` -- see isOn -- determines if a point belongs to a variety
  - `isOn(AbstractPoint,WitnessSet)` -- see isOn -- determines if a point belongs to a variety
  - `isOn(AbstractPoint,WitnessSet,ZZ)` -- see isOn -- determines if a point belongs to a variety
  - isSolution(AbstractPoint,PolySystem) -- check if a point satisfies a polynomial system approximately
  - isSubset(NumericalVariety,NumericalVariety) -- check containment
  - `isSubset(WitnessSet,WitnessSet)` -- see isSubset(NumericalVariety,NumericalVariety) -- check containment
  - jacobian(GateSystem) -- jacobian of a (gate) system
  - `jacobian(List,GateSystem)` -- see jacobian(GateSystem) -- jacobian of a (gate) system
  - NAGtrace(ZZ) -- set the trace level in NumericalAlgebraicGeometry package
  - `newton(System,AbstractPoint)` -- see newton -- Newton-Raphson method
  - `hypersurfaceSection(NumericalVariety,RingElement)` -- see numericalIntersection -- intersection of numerical varieties
  - `numericalIntersection(NumericalVariety,Ideal)` -- see numericalIntersection -- intersection of numerical varieties
  - `numericalIntersection(NumericalVariety,NumericalVariety)` -- see numericalIntersection -- intersection of numerical varieties
  - `numericalIntersection(WitnessSet,WitnessSet)` -- see numericalIntersection -- intersection of numerical varieties
  - numericalIrreducibleDecomposition(Ideal) -- constructs a numerical variety defined by the given ideal
  - numParameters(ParameterHomotopy) -- the number of parameters in the parameter homotopy
  - numVariables(ParameterHomotopy) -- the number of variables in the parameter homotopy
  - numVariables(SpecializedParameterHomotopy) -- the number of variables in the parameter homotopy
  - parameterHomotopy(List,List,List) -- solve a parametric system of equations
  - parameters(GateSystem) -- the parameter gates in the evaluation circuit used for the system
  - parameters(ParameterHomotopy) -- the parameters in the parameter homotopy
  - `parametricSegmentHomotopy(GateSystem)` -- see parametricSegmentHomotopy -- creates an ansatz for a segment homotopy
  - `parametricSegmentHomotopy(PolySystem)` -- see parametricSegmentHomotopy -- creates an ansatz for a segment homotopy
  - polySystem(GateSystem,PolynomialRing) -- classical polynomial system associated to a gate system
  - `randomInitialPair(List)` -- see randomInitialPair -- a random initial pair
  - randomSd(List) -- a random homogeneous system of polynomial equations
  - `refine(AbstractPoint)` -- see refine(List,List) -- refine numerical solutions to a system of polynomial equations
  - refine(List,List) -- refine numerical solutions to a system of polynomial equations
  - `refine(PolySystem,AbstractPoint)` -- see refine(List,List) -- refine numerical solutions to a system of polynomial equations
  - `refine(PolySystem,List)` -- see refine(List,List) -- refine numerical solutions to a system of polynomial equations
  - regeneration(List) -- solve a system of polynomial equations with regeneration method
  - removeRedundantComponents(NumericalVariety) -- remove redundant components
  - sample(WitnessSet) -- sample a point on a component
  - `segmentHomotopy(GateSystem,GateSystem)` -- see segmentHomotopy -- a segment homotopy
  - `segmentHomotopy(List,List)` -- see segmentHomotopy -- a segment homotopy
  - `segmentHomotopy(PolySystem,PolySystem)` -- see segmentHomotopy -- a segment homotopy
  - `getDefault(Symbol)` -- see setDefault -- set/get the default parameters for continuation algorithms
  - solveGenericSystemInTorus(List) -- solve a generic system of sparse polynomial equations in the torus
  - `solveGenericSystemInTorus(PolySystem)` -- see solveGenericSystemInTorus(List) -- solve a generic system of sparse polynomial equations in the torus
  - solveSystem(List) -- solve a system of polynomial equations
  - `solveSystem(PolySystem)` -- see solveSystem(List) -- solve a system of polynomial equations
  - specialize(GateSystem,AbstractPoint) -- specialize parameters in a gate system
  - specialize(ParameterHomotopy,Matrix) -- specialize a parameter homotopy
  - `squareUp(AbstractPoint,AbstractPoint,GateSystem)` -- see squareUp -- square up a polynomial system
  - `squareUp(AbstractPoint,GateSystem)` -- see squareUp -- square up a polynomial system
  - `squareUp(System)` -- see squareUp -- square up a polynomial system
  - `squareUp(System,Matrix)` -- see squareUp -- square up a polynomial system
  - `squareUp(System,ZZ)` -- see squareUp -- square up a polynomial system
  - totalDegreeStartSystem(List) -- construct a start system for the total degree homotopy
  - track(List,List,List) -- track a linear segment homotopy given start and target system
  - `track(PolySystem,PolySystem,List)` -- see track(List,List,List) -- track a linear segment homotopy given start and target system
  - trackHomotopy(Homotopy,List) -- follow points along a homotopy
  - `trackHomotopy(Matrix,List)` -- see trackHomotopy(Homotopy,List) -- follow points along a homotopy
  - `trackHomotopy(Sequence,List)` -- see trackHomotopy(Homotopy,List) -- follow points along a homotopy
  - union(NumericalVariety,NumericalVariety) -- union of numerical varieties
  - vars(GateSystem) -- the variable gates in the evaluation circuit used for the system
- Symbols
  - AffinePatches -- reserved for developers
  - `CompiledHornerForm` -- see AffinePatches -- reserved for developers
  - `DynamicPatch` -- see AffinePatches -- reserved for developers
  - `HornerForm` -- see AffinePatches -- reserved for developers
  - `SLP` -- see AffinePatches -- reserved for developers
  - `SLPcorrector` -- see AffinePatches -- reserved for developers
  - `SLPpredictor` -- see AffinePatches -- reserved for developers
  - BERTINI -- use Bertini for homotopy continuation
  - Certified -- a value for the option Predictor that triggers certified tracking
  - `Deflation` -- see deflate -- first-order deflation
  - `DeflationRandomMatrix` -- see deflate -- first-order deflation
  - `DeflationSequence` -- see deflate -- first-order deflation
  - `DeflationSequenceMatrices` -- see deflate -- first-order deflation
  - `LiftedPoint` -- see deflate -- first-order deflation
  - `LiftedSystem` -- see deflate -- first-order deflation
  - `SolutionSystem` -- see deflate -- first-order deflation
  - `SquareUp` -- see deflate -- first-order deflation
  - `GeneralPosition` -- see goodInitialPair(List) -- make an initial pair conjectured to be good by Shub and Smale
  - HOM4PS2 -- use HOM4PS for homotopy continuation
  - `Bits` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `CorrectorTolerance` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `EndZoneFactor` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `ErrorTolerance` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `Euler` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `gamma` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `InfinityThreshold` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `Iterations` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `maxCorrSteps` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `Multistep` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `MultistepDegree` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `NoOutput` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `numberSuccessesBeforeIncrease` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `Predictor` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `Projectivize` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `ResidualTolerance` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `RungeKutta4` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `Secant` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `stepIncreaseFactor` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `Tangent` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `tDegree` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `tStep` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - `tStepMin` -- see numerical homotopy tracking options -- options for core functions of Numerical Algebraic Geometry
  - Parameters -- a collection of parameters
  - PHCPACK -- use PHCpack for homotopy continuation
  - `Output` -- see regeneration(List) -- solve a system of polynomial equations with regeneration method
  - `Attempts` -- see setDefault -- set/get the default parameters for continuation algorithms
  - `SingularConditionNumber` -- see setDefault -- set/get the default parameters for continuation algorithms
  - `M2` -- see Software -- specify internal or external software
  - `M2engine` -- see Software -- specify internal or external software
  - `M2enginePrecookedSLPs` -- see Software -- specify internal or external software
  - Software -- specify internal or external software
  - `PostProcess` -- see solveSystem(...,PostProcess=>...) -- specifies whether to postprocess the solutions
  - `SquaredUpSystem` -- see squareUp -- square up a polynomial system
  - `SquareUpMatrix` -- see squareUp -- square up a polynomial system
  - `Field` -- see trackHomotopy(Homotopy,List) -- follow points along a homotopy
- Other things
  - DoublePrecision -- a constant equal to 53 (the number of bits of precision)

## For the programmer

The object NumericalAlgebraicGeometry is a package, defined in NumericalAlgebraicGeometry.m2, with auxiliary files in NumericalAlgebraicGeometry/.

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