Solving Polynomial Systems by Intersecting Subsystems
Abstract:
A diagonal homotopy can compute the witness set for the intersection of two
irreducible algebraic sets. This capability can be employed to compute the
solution of a system of polynomial equations by intersecting the varieties
defined by subsets of the equations. To intersect two such subsystems, one
must apply the diagonal homotopy pairwise to the irreducible components of
the solutions of the subsystems, followed by membership tests to eliminate
duplications. We describe how to organize this in general and then
specialize to the case where one of the subsystems is a hypersurface, given
by a single equation. A natural consequence is that one may find all
isolated solutions of a polynomial system by introducing the equations
one-by-one, carrying forward only the components of appropriate dimension
for the next stage of computation. Experiments with highly structured
polynomial systems show that this approach is very effective, capturing,
for example, much of the sparsity of the equations without analyzing their
monomial structure. This holds much promise for the efficient treatment of
systems arising in applications, in which the equations may have intricate
structures not easily exploited by previous techniques.