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

LI Haokun, XIA Bican, ZHAO Tianqi

系统科学与复杂性(英文) ›› 2023, Vol. 36 ›› Issue (6) : 2661-2680.

PDF(346 KB)
中国科学院数学与系统科学研究院期刊网
JSSC
PDF(346 KB)
系统科学与复杂性(英文) ›› 2023, Vol. 36 ›› Issue (6) : 2661-2680. DOI: 10.1007/s11424-023-2260-3

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

    LI Haokun, XIA Bican, ZHAO Tianqi
作者信息 +

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

    LI Haokun, XIA Bican, ZHAO Tianqi
Author information +
文章历史 +

摘要

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öbner 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.

Abstract

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öbner 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öbner basis / pure chain / square-free pure chain / triangular decomposition / zero-dimensional polynomial system

Key words

Gröbner basis / pure chain / square-free pure chain / triangular decomposition / zero-dimensional polynomial system

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
LI Haokun , XIA Bican , ZHAO Tianqi. Square-Free Pure Triangular Decomposition of Zero-Dimensional Polynomial Systems. 系统科学与复杂性(英文), 2023, 36(6): 2661-2680 https://doi.org/10.1007/s11424-023-2260-3
LI Haokun , XIA Bican , ZHAO Tianqi. Square-Free Pure Triangular Decomposition of Zero-Dimensional Polynomial Systems. Journal of Systems Science and Complexity, 2023, 36(6): 2661-2680 https://doi.org/10.1007/s11424-023-2260-3

参考文献

[1] Wu W, On the decision problem and the mechanization of theorem-proving in elementary geometry, Scientia Sinica, 1978, 21(2):159-172.
[2] Wu W, Basic principles of mechanical theorem proving in elementary geometries, Journal of Systems Science and Mathematical Sciences, 1984, 4(3):207-235.
[3] Chou S and Gao X, Ritt-wu's decomposition algorithm and geometry theorem proving, CADE 1990, Springer, 1990, 207-220.
[4] Yang L and Zhang J, Searching dependency between algebraic equations:An algorithm applied to automated reasoning, Technical report, ICTP, 1991.
[5] Yang L, Zhang J, and Hou X, A criterion of dependency between algebraic equations and its applications, Proc. IWMM, 1992, 110-134.
[6] Xia B and Yang L, An algorithm for isolating the real solutions of semi-algebraic systems, J. Symb. Comput., 2002, 34(5):461-477.
[7] Xia B and Zhang T, Real solution isolation using interval arithmetic, Comput. Math. Appl., 2006, 52(6-7):853-860.
[8] Wu W and Gao X, Automated reasoning and equation solving with the characteristic set method, J. Comput. Sci. Tech., 2006, 21(5):756-764.
[9] Boulier F, Chen C, Lemaire F, et al., Real root isolation of regular chains, Computer Mathematics, Springer Berlin Heidelberg, 2014:33-48.
[10] Gao X, An introduction to wu's method of mechanical geometry theorem proving, Proc. IFIP TC12/WG12.3, 1992, 13-22.
[11] Cheng J, Gao X, and Guo L, Root isolation of zero-dimensional polynomial systems with linear univariate representation, J. Symb. Comput., 2012, 47(7):843-858.
[12] Xia B and Yang L, Automated Inequality Proving and Discovering, World Scientific, Singapore, 2016.
[13] Chen Z, Tang X, and Xia B, Generic regular decompositions for parametric polynomial systems, Journal of Systems Science & Complexity, 2015, 28(5):1194-1211.
[14] Wang D, Elimination Methods, Springer Science & Business Media, 2001.
[15] Aubry P, Lazard D, and Maza M M, On the theories of triangular sets, J. Symb. Comput., 1999, 28(1-2):105-124.
[16] Kalkbrener M, A generalized euclidean algorithm for computing triangular representations of algebraic varieties, J. Symb. Comput., 1993, 15(2):143-167.
[17] Wang D, Zero decomposition algorithms for systems of polynomial equations, Computer Mathematics, World Scientific, Singapore, 2000, 67-70.
[18] Wang D, Solving polynomial equations:Characteristic sets and triangular systems, Math. Comput. Simulation, 1996, 42(4-6):339-351.
[19] Dong R and Mou C, On characteristic decomposition and quasi-characteristic decomposition, CASC 2019, Cham:Springer International Publishing, 2019, 122-139.
[20] Wang D, Computing triangular systems and regular systems, J. Symb. Comput., 2000, 30(2):221-236.
[21] Dong R and Mou C, Decomposing polynomial sets simultaneously into gröbner bases and normal triangular sets, CASC 2017, Springer International Publishing, 2017:77-92.
[22] Chen C, Solving polynomial systems via triangular decomposition, PhD thesis, The University of Western Ontario, London, 2011.
[23] Hubert E, Notes on triangular sets and triangulation-decomposition algorithms i:Polynomial systems, International Conference on Symbolic and Numerical Scientific Computation, Springer, 2001, 1-39.
[24] Chen C and Maza M M, Algorithms for computing triangular decomposition of polynomial systems, J. Symb. Comput., 2012, 47(6):610-642.
[25] Buchberger B, Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal, PhD thesis, Universitat Insbruck, 1965.
[26] Hashemi A and Lazard D, Complexity of zero-dimensional gröbner bases, PhD thesis, INRIA, 2005.
[27] Lakshman Y N, A single exponential bound on the complexity of computing gröbner bases of zero dimensional ideals, Effective Methods in Algebraic Geometry, Springer, Birkhäuser Boston, 1991, 227-234.
[28] Faugere J C, A new efficient algorithm for computing gröbner bases (f4), J. Pure Appl. Algebra, 1999, 139(1-3):61-88.
[29] Faugere J C, A new efficient algorithm for computing gröbner bases without reduction to zero (f5), Proc. ISSAC'02, 2002, 75-83.
[30] Lazard D, Solving zero-dimensional algebraic systems, J. Symb. Comput., 1992, 13(2):117-131.
[31] Möller H M, On decomposing systems of polynomial equations with finitely many solutions, Applicable Algebra in Engineering, Communication and Computing, 1993, 4(4):217-230.
[32] Wang D, On the connection between ritt characteristic sets and buchberger-gröbner bases, Math. Comput. Sci., 2016, 10(4):479-492.
[33] Becker T and Weispfenning V, Gröbner Bases, Springer, New York, 1998.
[34] Cox D, Little J, and OShea D, Ideals, Varieties, and Algorithms:An Introduction to Computational Algebraic Geometry and Commutative Algebra, 4th ed, Springer Science & Business Media, Berlin, 2013.
[35] Cox D A, Little J B, and OShea D, Using Algebraic Geometry, Graduate texts in mathematics, 2nd Edition, Springer Science & Business Media, 2005.
[36] Boulier F, Lemaire F, and Maza M M, Well known theorems on triangular systems and the d5 principle, TC, 2006, 79-91.

基金

This research was supported by National Key R&D Program of China under Grant No. 2022YFA1005102 and the National Natural Science Foundation of China under Grant No. 61732001.
PDF(346 KB)

87

Accesses

0

Citation

Detail
段落导航
相关文章

/

〈 〉