2022/02/12 by Haokun Li, Li, Haokun, Bican Xia +3
Computer Science · Mathematics · #Commutative Algebra and Its Applications #FOS: Computer and information sciences #Formal Methods in Verification #Polynomial and algebraic computation #Symbolic Computation (cs.SC) #cs.SC
paper · pdf · doi:10.48550/arxiv.2202.06044
arxiv created 2022/02/12 · openalex publication_date 2022/02/12 · arxiv updated 2022/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.