PHCpack -- a package for Polynomial Homotopy Continuation

Description

This package provides an interface to the software PHCpack, a general-purpose polynomial system solver that uses homotopy continuation. The main method is a numerical blackbox solver, implemented for Laurent systems. The package also provides a fast mixed volume computation, the ability to filter solutions, extract real solutions, or track solution paths defined by a polynomial homotopy. For positive dimensional solution sets, we can compute a numerical irreducible decomposition.

The software PHCpack itself is available at http://www.math.uic.edu/~jan/download.html. This site provides source code and its executable version phc. To use the methods from this package, the user must have the executable program phc available, preferably in the execution path. The functions in this package call the phc executable, behind the scenes, with appropriate input options, and save intermediate output to temporary files. For convenience, the file names are displayed, and the commands that are invoked are documented under "Consequences" for each function.

Below is a simple example using the most popular function, the numerical blackbox solver.

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

o1 = R

o1 : PolynomialRing

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

         2         3
o2 = {- x  + y, - x  + z, x + y + z - 1}

o2 : List

i3 : solns = solveSystem(system)

o3 = {{-.771845-1.11514*ii, -.647799+1.72143*ii, 2.41964-.606291*ii},
     ------------------------------------------------------------------------
     {.543689, .295598, .160713}, {-.771845+1.11514*ii, -.647799-1.72143*ii,
     ------------------------------------------------------------------------
     2.41964+.606291*ii}}

o3 : List

i4 : numSolns = #solns

o4 = 3

i5 : solns/print
{-.771845-1.11514*ii, -.647799+1.72143*ii, 2.41964-.606291*ii}
{.543689, .295598, .160713}
{-.771845+1.11514*ii, -.647799-1.72143*ii, 2.41964+.606291*ii}

o5 = {, , }

o5 : List

We see that there are three solutions to the above system. Each solution is of type Point and contains diagnostic information about the quality of the solution.

i6 : oneSoln = solns_0

o6 = oneSoln

o6 : Point

i7 : peek oneSoln

o7 = Point{cache => CacheTable{...3...}                             
           Coordinates => {-.771845-1.11514*ii, -.647799+1.72143*ii,
     ------------------------------------------------------------------------
                        }
     2.41964-.606291*ii}

The value of LastT is the end value of the continuation parameter: if it equals 1, then the solver reached the end of the path properly.

Contributors

Caveat

1. If you are having trouble installing the package, check whether the path to your PHCpack executable was set correctly. You can check this by typing the following command:

options PHCpack

If it is wrong, you can update it by putting the absolute path into the init-PHCpack.m2 file, For example, if the executable phc is located in C:/cygwin/PHC, then the line inside the init-PHCpack.m2 file will look like this:

"path" => "C:/cygwin/PHC/" .

Alternately, the path could be set when loading the package using the following command:

loadPackage ("PHCpack", Configuration=>{"path"=>"C:/cygwin/PHC/","PHCexe"=>"./phc"})

2. The current version 1.8 of PHCpack.m2 was developed with version 1.9 of Macaulay2 and with version 2.4.17 of phc.

Authors

Certification

Version 1.6 of this package was accepted for publication in volume 5 of The Journal of Software for Algebra and Geometry on 2013-07-11, in the article Interfacing with PHCpack (DOI: 10.2140/jsag.2013.5.20). That version can be obtained from the journal or from the Macaulay2 source code repository.

Version

This documentation describes version 1.8 of PHCpack.

Source code

The source code from which this documentation is derived is in the file PHCpack.m2. The auxiliary files accompanying it are in the directory PHCpack/.

Exports

Functions and commands
- cascade -- runs a cascade of homotopies to get witness sets for the variety
- constructEmbedding -- constructs an embedding of a polynomial system
- factorWitnessSet -- applies monodromy to factor a witness set into irreducible components
- intersectSlice -- intersects a witness set by a slice
- isCoordinateZero -- checks if coordinate has absolute value less than a given tolerance
- isWitnessSetMember -- tests whether a point belongs to a solution set
- mixedVolume -- computes mixed volume of a polynomial system
- nonZeroFilter -- returns solutions with coordinate larger than given tolerance
- numericalIrreducibleDecomposition -- finds the irreducible components of the zero set of a system of polynomials
- realSlice1D -- computes a real slice for a one dimensional witness set
- realSlice2D -- computes a real slice for a two dimensional witness set
- refineSolutions -- refines solutions of a system by increasing working precision
- solveRationalSystem -- approximates solutions to a rational system of equations
- solveSystem -- a numerical blackbox solver
- toLaurentPolynomial -- converts a list of rational polynomials into Laurent polynomials
- topWitnessSet -- returns a witness set and nonsolutions for the top dimensional solution set
- trackPaths -- tracks paths defined by a typical homotopy between start and end systems
- versionNumber -- returns the version number and release date of phc
- zeroFilter -- returns solutions with k-th coordinate less than the given tolerance
Methods
- cascade(List) -- see cascade -- runs a cascade of homotopies to get witness sets for the variety
- constructEmbedding(List,ZZ) -- see constructEmbedding -- constructs an embedding of a polynomial system
- factorWitnessSet(WitnessSet) -- see factorWitnessSet -- applies monodromy to factor a witness set into irreducible components
- intersectSlice(WitnessSet,List) -- see intersectSlice -- intersects a witness set by a slice
- isCoordinateZero(AbstractPoint,ZZ,RR) -- see isCoordinateZero -- checks if coordinate has absolute value less than a given tolerance
- isWitnessSetMember(WitnessSet,AbstractPoint) -- see isWitnessSetMember -- tests whether a point belongs to a solution set
- nonZeroFilter(List,ZZ,RR) -- see nonZeroFilter -- returns solutions with coordinate larger than given tolerance
- numericalIrreducibleDecomposition(List) -- see numericalIrreducibleDecomposition -- finds the irreducible components of the zero set of a system of polynomials
- realSlice1D(WitnessSet) -- see realSlice1D -- computes a real slice for a one dimensional witness set
- realSlice2D(WitnessSet) -- see realSlice2D -- computes a real slice for a two dimensional witness set
- refineSolutions(List,List,ZZ) -- see refineSolutions -- refines solutions of a system by increasing working precision
- solveRationalSystem(List) -- see solveRationalSystem -- approximates solutions to a rational system of equations
- solveSystem(List) -- see solveSystem -- a numerical blackbox solver
- toLaurentPolynomial(List,Symbol) -- see toLaurentPolynomial -- converts a list of rational polynomials into Laurent polynomials
- topWitnessSet(List,ZZ) -- see topWitnessSet -- returns a witness set and nonsolutions for the top dimensional solution set
- trackPaths(List,List,List) -- see trackPaths -- tracks paths defined by a typical homotopy between start and end systems
- versionNumber(Nothing) -- see versionNumber -- returns the version number and release date of phc
- zeroFilter(List,ZZ,RR) -- see zeroFilter -- returns solutions with k-th coordinate less than the given tolerance
Symbols
- computingPrecision -- flag to switch to double double or quad double precision
- gamma -- the constant in the gamma trick, optional input for trackPaths
- interactive -- flag to run phc -p or phc -m in interactive mode
- intermediateSolutions -- option of trackPaths to get all intermediate solutions on a path
- loadSettingsPath -- option of trackPaths to load the settings for a reproducible rerun
- numThreads -- the number of threads in the path tracker
- randomSeed -- seed for the random number generators
- saveSettingsPath -- option of trackPaths to save the settings for a reproducible rerun
- searchDelta -- option of realSlice1D
- searchNpoints -- option of realSlice1D
- searchTolerance -- option of realSlice1D
- seeProgress -- flag to monitor the progress of the multithreaded path tracker
- StableMixedVolume -- optional input for computation of the stable mixed volume
- StartDimension -- optional input for cascade and numericalIrreducibleDecomposition
- StartSystem -- optional input to construct and solve a random coefficient system
- tDegree -- the degree of the continuation parameter

For the programmer

The object PHCpack is a package.