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.