Computing monodromy via parallel homotopy continuation

Numerical homotopy continuation gives a powerful tool for the applied scientist who seeks solutions to a system of polynomial equations. Techniques from numerical homotopy continuation can also be useful in pure mathematical research. We discuss applications of a particular homotopy continuation idea that leads to probabilistic numerical algorithms for construction of monodromy groups. One such application is used to analyze positive-dimensional solutions of polynomial systems. It is called the monodromy breakup method and partitions a witness set representing a positive-dimensional solution into irreducible components. The first author in collaboration with Jan Verschelde has implemented two parallel versions of this algorithm which show good speedup. We use numerical homotopy continuation to compute Galois groups of certain enumerative geometric problems coming from Schubert calculus.The basic idea is similar: given a parametric family of 0-dimensional polynomial systems, we construct loops in the parameter space, follow the solution paths along these loops to obtain a permutation of the set of the solutions.These permutations are used to compute the subgroup of the full symmetric group that they generate. Copyright 2007 ACM.

Overview