MonodromySolver -- solve polynomial systems via homotopy continuation and monodromy

Description

This package provides randomized numerical methods for finding complex solutions to systems of polynomial equations. The main methods implemented in this package find solutions to polynomial systems of equations over the complex numbers. As described in "Solving polynomial systems via homotopy continuation and monodromy" (2016), these methods pair numerical homotopy continuation with the transitive monodromy action of a suitable covering map.

It includes several blackbox functions based on these methods.

The most basic interface is provided by the method sparseMonodromySolve. More advanced solvers can be applied to linearly parametrized families. The family in the example below is the 5-variable Reimer system from the Posso test suite: the generic solution count is 144, while the Bezout number and mixed volume are both 720.

 ```i1 : setRandomSeed 0 o1 = 0``` ```i2 : R = CC[a_1..a_5,b_1..b_5][x,y,z,t,u] o2 = R o2 : PolynomialRing``` ```i3 : P = polySystem {-a_1+b_1*(x^2-y^2+z^2+u^2-t^2),-a_2+b_2*(x^3-y^3+z^3+u^3-t^3),-a_3+b_3*(x^4-y^4+z^4+u^4-t^4),-a_4+b_4*(x^5-y^5+z^5+u^5-t^5), -a_5+b_5*(x^6-y^6+z^6+u^6-t^6)} o3 = P o3 : PolySystem``` ```i4 : (N,npaths) = monodromySolve P o4 = (HomotopyNode{...5...}, 576) o4 : Sequence``` ```i5 : first N.SpecializedSystem -- (the first polynomial of) a randomly generated system in the family defined by P 2 2 o5 = (- .272372 - .962192*ii)x + (.272372 + .962192*ii)y + (- .272372 - ------------------------------------------------------------------------ 2 2 2 .962192*ii)z + (.272372 + .962192*ii)t + (- .272372 - .962192*ii)u - ------------------------------------------------------------------------ .841103 + .540875*ii o5 : CC [x, y, z, t, u] 53``` ```i6 : first N.PartialSols -- a solution to N.SpecializedSystem o6 = {.851837+.102702*ii, -.312865+.878644*ii, .053494+.506022*ii, -.606275-.104337*ii, -.208647-.72906*ii} o6 : Point``` ```i7 : npaths -- total number of paths tracked in call to monodromySolve o7 = 576```

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 underlying graph is "seeded" automatically. The current seeding implementation will fail, for instance, in cases where there are equations without parameters. In such a case, the user may find a seed pair themselves (see monodromySolve(PolySystem,Point,List) for an example.)

Authors

• Timothy Duff
• Cvetelina Hill
• Anders Nedergaard Jensen
• Kisun Lee
• Anton Leykin
• Jeff Sommars

Version

This documentation describes version 1.11 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/.