Square-Free Pure Triangular Decomposition of Zero-Dimensional Polynomial Systems  

作　　者：LI Haokun XIA Bican ZHAO Tianqi 

机构地区：[1]School of Mathematical Sciences,Peking University,Beijing,100871,China

出　　处：《Journal of Systems Science & Complexity》2023年第6期2661-2680,共20页系统科学与复杂性学报（英文版）

基　　金：supported by National Key R&D Program of China under Grant No.2022YFA1005102;the National Natural Science Foundation of China under Grant No.61732001。

摘　　要：Triangular decomposition with different properties has been used for various types of problem solving.In this paper,the concepts of pure chains and square-free pure triangular decomposition(SFPTD)of zero-dimensional polynomial systems are defined.Because of its good properties,SFPTD may be a key way to many problems related to zero-dimensional polynomial systems.Inspired by the work of Wang(2016)and of Dong and Mou(2019),the authors propose an algorithm for computing SFPTD based on Gr¨obner bases computation.The novelty of the algorithm is that the authors make use of saturated ideals and separant to ensure that the zero sets of any two pure chains are disjoint and every pure chain is square-free,respectively.On one hand,the authors prove 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,the authors 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 pseudodivision,and the methods based on SFPTD for real solution isolation and for computing radicals of zero-dimensional ideals are very efficient.

关 键 词：Gr¨obner basis pure chain square-free pure chain triangular decomposition zero-dimensional polynomial system 

分 类 号：O174.14[理学—数学]