MonodromySolver -- solve polynomial systems via homotopy continuation and monodromy

Description

This packages provides randomized methods for numerically solving polynomial systems of equations that occur in parametric families, by exploiting the transitive action of an associated monodromy group. The package implements the graph-based framework described in the third reference below. There are three main functions that may be used to solve a system of a family of systems:

solveFamily -- a solver for parametric families with simple output
sparseMonodromySolve -- an "out of the box" polynomial system solver
monodromySolve -- the main function of the MonodromySolver package

monodromySolve is the core function, whose input may be a polynomial system or $ofClass GateSystem$. As an additional input, a seed pair consisting of initial parameter and solution values may be provided. solveFamily is a wrapper function that returns specific solutions and parameter values. sparseMonodromySolve is a blackbox solver for systems without parameters, that calls the core function. These functions have many options in common, which are summarized in MonodromySolverOptions. Here is an example illustrating how to solve a parametric family for specific parameter values.

i1 : setRandomSeed 0;

i2 : declareVariable \ {A,B,C,D,X,Y};

i3 : F = gateSystem(matrix{{A,B,C,D}},matrix{{X,Y}},matrix{{A*(X-1)^2-B}, {C*(Y+2)^2+D}});

i4 : p0 = point{{1,1,1,1}};

i5 : sols = solveFamily(p0, F, NumberOfNodes=>3);

i6 : for i from 0 to 3 list norm(evaluate(F, p0, sols#i))

o6 = {4.39145e-23, 4.39145e-23, 4.39145e-23, 4.39145e-23}

o6 : List

Each solver works by assembling randomly generated systems within a HomotopyGraph and tracking paths between them. They are also equipped with a number of options, which may be useful for speeding up computation or increasing the probability of success.

In the example above, the system is linear in parameters, allowing for the seed pair to be computed automatically. The current seeding implementation will report failure in other cases. Depending on the problem of interest, there may still be a natural way to generate the seed pair, as in monodromySolve(System,AbstractPoint,List).

Some references for numerical monodromy methods:

Sommese, Andrew J., Jan Verschelde, and Charles W. Wampler. "Numerical decomposition of the solution sets of polynomial systems into irreducible components." SIAM Journal on Numerical Analysis 38.6 (2001): 2022-2046.

del Campo, Abraham Martin, and Jose Israel Rodriguez. "Critical points via monodromy and local methods." Journal of Symbolic Computation 79 (2017): 559-574.

Duff, Timothy, Cvetelina Hill, Anders Jensen, Kisun Lee, Anton Leykin, and Jeff Sommars. "Solving polynomial systems via homotopy continuation and monodromy." IMA Journal of Numerical Analysis 39.3 (2019): 1421-1446.

Authors

Timothy Duff <[email protected]>
Cvetelina Hill <[email protected]>
Anders Nedergaard Jensen <[email protected]>
Kisun Lee <[email protected]>
Anton Leykin <[email protected]>
Jeff Sommars <[email protected]>

Version

This documentation describes version 1.16 of MonodromySolver.

Source code

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

Exports

Types
- HomotopyGraph
- HomotopyNode
- PointArray -- a container for solutions
Functions and commands
- appendPoint -- append a point at the end of a PointArray
- appendPoints -- append a list of points at the end of a PointArray
- completeGraphAugment -- augment graph with the complete graph structure
- completeGraphInit -- initialize the topology of a complete graph
- computeMixedVolume -- compute mixed volume via Gfan
- createSeedPair -- create initial seed for the homotopy continuation
- dynamicFlowerSolve -- a naive dynamic strategy
- flowerGraphAugment -- augment graph with the flower graph structure
- flowerGraphInit -- solve via monodromy by using flower shaped graph
- getTrackTime -- elapsed time taken by solver
- homotopyGraph -- HomotopyGraph Constructor
- makeBatchPotential -- batch sensitive potentialE
- monodromyGroup -- compute the group of permutations implicitly defined by a homotopy graph
- monodromySolve -- the main function of the MonodromySolver package
- pointArray -- constructor for PointArray
- potentialE -- the "expected" potential of an edge
- potentialLowerBound -- the potential which is equal to the minimal number of new points guaranteed to be discovered
- selectBestEdgeAndDirection -- selects edge and direction based on highest potential for obtaining new information
- selectRandomEdgeAndDirection -- random selection of edge and direction for homotopy
- solveFamily -- a solver for parametric families with simple output
- sparseMonodromySolve -- an "out of the box" polynomial system solver
- specializeSystem -- specialize parametric system at a point in the parameter space.
Methods
- appendPoint(PointArray,AbstractPoint) -- see appendPoint -- append a point at the end of a PointArray
- appendPoints(PointArray,List) -- see appendPoints -- append a list of points at the end of a PointArray
- computeMixedVolume(List) -- see computeMixedVolume -- compute mixed volume via Gfan
- createSeedPair(System) -- see createSeedPair -- create initial seed for the homotopy continuation
- createSeedPair(System,AbstractPoint) -- see createSeedPair -- create initial seed for the homotopy continuation
- getTrackTime(HomotopyGraph) -- see getTrackTime -- elapsed time taken by solver
- indices(PointArray) -- returns indices of a PointArray
- isMember(AbstractPoint,PointArray) -- test point membership in a PointArray
- length(PointArray) -- number of items stored in a PointArray
- monodromyGroup(System) -- see monodromyGroup -- compute the group of permutations implicitly defined by a homotopy graph
- monodromyGroup(System,AbstractPoint,List) -- see monodromyGroup -- compute the group of permutations implicitly defined by a homotopy graph
- monodromySolve(System) -- the main function of the MonodromySolver package
- monodromySolve(System,AbstractPoint,List) -- the main function of the MonodromySolver package
- net(PointArray) -- pretty printing
- solveFamily(AbstractPoint,System) -- see solveFamily -- a solver for parametric families with simple output
- solveFamily(System) -- see solveFamily -- a solver for parametric families with simple output
- sparseMonodromySolve(PolySystem) -- see sparseMonodromySolve -- an "out of the box" polynomial system solver
- specializeSystem(AbstractPoint,Matrix) -- see specializeSystem -- specialize parametric system at a point in the parameter space.
- specializeSystem(AbstractPoint,PolySystem) -- see specializeSystem -- specialize parametric system at a point in the parameter space.
Symbols
- PartialSols -- see HomotopyNode
- SpecializedSystem -- see HomotopyNode
- AugmentEdgeCount -- see MonodromySolverOptions
- AugmentGraphFunction -- see MonodromySolverOptions
- AugmentNodeCount -- see MonodromySolverOptions
- AugmentNumberOfRepeats -- see MonodromySolverOptions
- BatchSize -- see MonodromySolverOptions
- EdgesSaturated -- see MonodromySolverOptions
- Equivalencer -- see MonodromySolverOptions
- FilterCondition -- see MonodromySolverOptions
- GraphInitFunction -- see MonodromySolverOptions
- MonodromySolverOptions
- NumberOfEdges -- see MonodromySolverOptions
- NumberOfNodes -- see MonodromySolverOptions
- NumberOfRepeats -- see MonodromySolverOptions
- PointArrayTol -- see MonodromySolverOptions
- Potential -- see MonodromySolverOptions
- Randomizer -- see MonodromySolverOptions
- SelectEdgeAndDirection -- see MonodromySolverOptions
- StoppingCriterion -- see MonodromySolverOptions
- TargetSolutionCount -- see MonodromySolverOptions

For the programmer

The object MonodromySolver is a package.