Decomposition Solutions Sets of Polynomial Systems with Homotopies
Jan Verschelde, University of Illinois at Chicago
Friday, June 8, 2001, at U. of Waterloo.
Abstract:
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.
|