论文标题
零维多项式系统的无方形强三角分解
Square-free Strong Triangular Decomposition of Zero-dimensional Polynomial Systems
论文作者
论文摘要
具有不同特性的三角分解已用于各种类型的问题解决，例如几何定理证明了零维多项式系统等的实际解隔离。由于其良好的特性，SFSTD可能是与零维多项式系统有关的许多问题的关键方法，例如真实的解决方案隔离和计算零维理想的自由基。受Wang和Dong和Mou的工作的启发，我们提出了一种基于Gröbner基础计算计算SFSTD的算法。该算法的新颖性在于，我们利用饱和的理想和分离剂来确保任何两个强链的零集没有相交，并且每个强链分别无平方。一方面，我们证明了新算法的算术复杂性可以是变量数量的平方中的单个指数，这似乎是三角分解方法的罕见复杂性分析结果之一。另一方面，我们通过实验表明，在文献中的大量示例中，新算法比基于伪分割的流行三角分解方法要高得多。此外，还表明，在这些示例中，基于SFSTD的实际溶液隔离和计算零维理想的自由基的方法非常有效。
Triangular decomposition with different properties has been used for various types of problem solving, e.g. geometry theorem proving, real solution isolation of zero-dimensional polynomial systems, etc. In this paper, the concepts of strong chain and square-free strong triangular decomposition (SFSTD) of zero-dimensional polynomial systems are defined. Because of its good properties, SFSTD may be a key way to many problems related to zero-dimensional polynomial systems, such as real solution isolation and computing radicals of zero-dimensional ideals. Inspired by the work of Wang and of Dong and Mou, we propose an algorithm for computing SFSTD based on Gröbner bases computation. The novelty of the algorithm is that we make use of saturated ideals and separant to ensure that the zero sets of any two strong chains have no intersection and every strong chain is square-free, respectively. On one hand, we prove that the arithmetic complexity of the new algorithm can be single exponential in the square of the number of variables, which seems to be among the rare complexity analysis results for triangular-decomposition methods. On the other hand, we show experimentally that, on a large number of examples in the literature, the new algorithm is far more efficient than a popular triangular-decomposition method based on pseudo-division. Furthermore, it is also shown that, on those examples, the methods based on SFSTD for real solution isolation and for computing radicals of zero-dimensional ideals are very efficient.
