Abstract | ||
---|---|---|
Many polynomial systems have solution sets comprised of 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. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1137/S0036142901397101 | SIAM J. Numerical Analysis |
Keywords | Field | DocType |
solution set,numerical algebraicgeometry,symmetric functions applied,newton identities,components of solutions,numerical algebraic geometry,traces,decomposing solution sets,symmetricfunc tions,monodromy,homotopy continuation,polynomial system,floating-point numerical process,generic points,different dimension,interpolating polynomial,computational speed,irreducible components,polynomial systems,newton interpolation,divided differences,numerical stability,embedding,multiple irreducible component,expensive procedure,symmetric function,divided difference,symmetric functions,floating point,generic point,irreducible component | Symmetric function,Mathematical optimization,Polynomial,Polynomial interpolation,Mathematical analysis,Algorithm,Divided differences,Solution set,Symmetric polynomial,Newton's identities,Numerical stability,Mathematics | Journal |
Volume | Issue | ISSN |
40 | 6 | 0036-1429 |
Citations | PageRank | References |
30 | 1.92 | 11 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrew J. Sommese | 1 | 412 | 39.68 |
Jan Verschelde | 2 | 676 | 64.84 |
Charles W. Wampler | 3 | 410 | 44.13 |