Symmetric Functions Applied to Decomposing Solution Sets of Polynomial Systems
Symmetric Functions Applied to Decomposing Solution Sets of Polynomial Systems
复制标题
DOI：
10.1137/s0036142901397101
复制
发表时间：
2002-06
期刊：
影响因子：
--
通讯作者：
A. Sommese;J. Verschelde;C. Wampler
中科院分区：
文献类型：
--
作者：
A. Sommese;J. Verschelde;C. Wampler
许多多项式系统的解集由多个不可约分量组成，可能具有不同的维数。数值代数几何的一个基本问题是使用浮点数值处理将这样的解集分解成其分量。先前的工作已经展示了如何生成保证包括来自每个组件的点的通用点集。此外，我们已经展示了如何单值可以用来有效地预测这些点的组件中的成员资格的分区。然而，确认这一预测需要对每个分量进行昂贵的采样过程，以找到在其上消失的插值多项式。本文从理论上证明并在实践中证明，线性迹线足以完成这一验证步骤，这大大提高了计算速度和数值稳定性。此外，在这种情况下，人们可能仍然希望计算插值多项式，我们展示了如何更有效地这样做，通过建立一个结构化的网格的样本，使用除差，并应用对称函数。几个测试问题说明了新方法的有效性。
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.