Deflation and certified isolation of singular zeros of polynomial systems
Deflation and certified isolation of singular zeros of polynomial systems
复制标题
DOI：
10.1145/1993886.1993925
复制
发表时间：
2011-01
期刊：
影响因子：
--
通讯作者：
Angelos Mantzaflaris;B. Mourrain
中科院分区：
文献类型：
--
作者：
Angelos Mantzaflaris;B. Mourrain
我们开发了一个新的符号数字算法的奇异孤立点的认证，使用其相关的本地环结构和认证的数值计算。提出了一种改进的求解逆系统的方法，避免了冗余计算，减少了求解中间线性系统的规模。我们得到一个一步放气技术，从描述的多重结构的差异。收缩系统可用于牛顿迭代格式，具有二次收敛性。从一个多项式系统和一个足够小的邻域，我们得到了一个标准的存在性和唯一性的奇异根的一个给定的多重结构，应用精心选择的符号扰动。标准的验证方法，例如基于区间算术和不动点定理，证明存在一个唯一的扰动系统的奇异根的域。应用拓扑度计算和分析的真实的分支的隐曲线说明了该方法。
We develop a new symbolic-numeric algorithm for the certification of singular isolated points, using their associated local ring structure and certified numerical computations. An improvement of an existing method to compute inverse systems is presented, which avoids redundant computation and reduces the size of the intermediate linear systems to solve. We derive a one-step deflation technique, from the description of the multiplicity structure in terms of differentials. The deflated system can be used in Newton-based iterative schemes with quadratic convergence. Starting from a polynomial system and a sufficiently small neighborhood, we obtain a criterion for the existence and uniqueness of a singular root of a given multiplicity structure, applying a well-chosen symbolic perturbation. Standard verification methods, based e.g. on interval arithmetic and a fixed point theorem, are employed to certify that there exists a unique perturbed system with a singular root in the domain. Applications to topological degree computation and to the analysis of real branches of an implicit curve illustrate the method.