Solving polynomial systems via homotopy continuation and monodromy

Solving polynomial systems via homotopy continuation and monodromy

Timothy Duff, Cvetelina Hill, Anders Jensen, Kisun Lee, Anton Leykin, and Jeffrey Sommars

We develop an algorithm to find all solutions of a generic system in a family of polynomial systems with parametric coefficients using numerical homotopy continuation and the action of the monodromy group. We argue that the expected number of homotopy paths that this algorithm needs to follow is roughly linear in the number of solutions. We demonstrate that our software implementation is competitive with the existing state-of-the-art methods implemented in other software packages.

Paper: arxiv.org/abs/1609.08722

Code:

MonodromySolver is a package for Macaulay2 (open source; github link to M2 packages)
All examples used in our experiments are here (see README).
Slower version: needs an installation of Macaulay2 version 1.9+ and packages from the link above.
Faster version: needs Macaulay2 version 1.10+. (To compile the most recent developers' version, follow instructions for NumericalAlgebraicGeometry.)

(Last updated: July 2017)