**Symmetric Functions Applied to Decomposing**

** Solution Sets of Polynomial Systems **

*Andrew J. Sommese*,
*Jan Verschelde*, and
*Charles W. Wampler*

#### Abstract:

Many polynomial systems have solution sets comprising
multiple irreducible components, possibly of different dimensions.
A fundamental problem of numerical algebraic geometry is to
decompose such a solution set, using floating-point numerical
processes, into its components. Prior work has shown how to
generate sets of generic points guaranteed to include points from
every component. Furthermore, we have shown how monodromy can be
used to efficiently predict the partition of these points by membership in the
components. However, confirmation of this prediction
required an expensive procedure of sampling each component
to find an interpolating polynomial that vanishes on it.
This paper proves theoretically and demonstrates in practice
that linear traces suffice for this verification
step, which gives great improvement in both computational speed and
numerical stability. Moreover, in the case that one may still
wish to compute an interpolating polynomial, we show how to
do so more efficiently by building
a structured grid of samples, using divided differences,
and applying symmetric functions. Several test problems illustrate
the effectiveness of the new methods.
**2000 Mathematics Subject Classification:**
Primary 65H10; Secondary 13P05, 14Q99, 68W30.

**keywords:**
Components of solutions, divided differences, embedding,
generic points, traces, homotopy continuation, irreducible components,
Newton identities, Newton interpolation, numerical algebraic geometry,
monodromy, polynomial system, symmetric functions.

*SIAM J. Numer. Anal.* 40(6):2026-2046, 2002.