next | previous | forward | backward | up | index | toc

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:

monodromySolve is the core function, whose input may be 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
• Cvetelina Hill
• Anders Nedergaard Jensen
• Kisun Lee
• Anton Leykin
• Jeff Sommars

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/.

For the programmer

The object MonodromySolver is .