Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

Decomposition Solutions Sets of Polynomial Systems with Homotopies
Jan Verschelde, University of Illinois at Chicago
Friday, June 8, 2001, at U. of Waterloo.


All isolated solutions of a polynomial system can be reached with homotopy continuation methods. We view the setup of the homotopy as a symbolic preprocessing step to the numerical path following. Recent research aims to apply homotopies to solve systems with components of solutions, such as curves and higher dimensional surfaces.

An embedding of the original system defines a sequence of homotopies whose solution paths lead to generic points on each positive dimensional component. With monodromy we classify the generic points along each irreducible component, hereby decomposing the solution set into irreducible components. Equations to represent each irreducible component are found by interpolation. This decomposition provides symbolic information in a numerical fashion.

Computational progress is achieved replacing expensive multi-precision arithmetic in the interpolation phase with numerically stable algorithms exploiting algebraic structure. For example, slice a planar curve defined by f(x,y)=0 with the line x = c (c is constant), then the sum of y-values at the intersection of the line with the curve is predicted by a linear polynomial in x. While a high degree of f requires multi-precision, machine arithmetic suffices to interpolate a linear polynomial. Performance is illustrated on the cyclic n-roots problem, adjacent minors of a general 2-by-n matrix, and a platform in mechanisms design.

This is ongoing joint work with Andrew Sommese and Charles Wampler.


Last modified on Sunday, 04 November 2012, at 15:42 hours.