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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Wu W, On the decision problem and the mechanization of theorem-proving in elementary geometry, Scientia Sinica, 1978, 21(2): 159–172.
Wu W, Basic principles of mechanical theorem proving in elementary geometries, Journal of Systems Science and Mathematical Sciences, 1984, 4(3): 207–235.
Chou S and Gao X, Ritt-wu’s decomposition algorithm and geometry theorem proving, CADE 1990, Springer, 1990, 207–220.
Yang L and Zhang J, Searching dependency between algebraic equations: An algorithm applied to automated reasoning, Technical report, ICTP, 1991.
Yang L, Zhang J, and Hou X, A criterion of dependency between algebraic equations and its applications, Proc. IWMM, 1992, 110–134.
Xia B and Yang L, An algorithm for isolating the real solutions of semi-algebraic systems, J. Symb. Comput., 2002, 34(5): 461–477.
Xia B and Zhang T, Real solution isolation using interval arithmetic, Comput. Math. Appl., 2006, 52(6–7): 853–860.
Wu W and Gao X, Automated reasoning and equation solving with the characteristic set method, J. Comput. Sci. Tech., 2006, 21(5): 756–764.
Boulier F, Chen C, Lemaire F, et al., Real root isolation of regular chains, Computer Mathematics, Springer Berlin Heidelberg, 2014: 33–48.
Gao X, An introduction to wu’s method of mechanical geometry theorem proving, Proc. IFIP TC12/WG12.3, 1992, 13–22.
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.
Xia B and Yang L, Automated Inequality Proving and Discovering, World Scientific, Singapore, 2016.
Chen Z, Tang X, and Xia B, Generic regular decompositions for parametric polynomial systems, Journal of Systems Science and Complexity, 2015, 28(5): 1194–1211.
Wang D, Elimination Methods, Springer Science & Business Media, 2001.
Aubry P, Lazard D, and Maza M M, On the theories of triangular sets, J. Symb. Comput., 1999, 28(1–2): 105–124.
Kalkbrener M, A generalized euclidean algorithm for computing triangular representations of algebraic varieties, J. Symb. Comput., 1993, 15(2): 143–167.
Wang D, Zero decomposition algorithms for systems of polynomial equations, Computer Mathematics, World Scientific, Singapore, 2000, 67–70.
Wang D, Solving polynomial equations: Characteristic sets and triangular systems, Math. Comput. Simulation, 1996, 42(4–6): 339–351.
Dong R and Mou C, On characteristic decomposition and quasi-characteristic decomposition, CASC 2019, Cham: Springer International Publishing, 2019: 122–139.
Wang D, Computing triangular systems and regular systems, J. Symb. Comput., 2000, 30(2): 221–236.
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.
Chen C, Solving polynomial systems via triangular decomposition, PhD thesis, The University of Western Ontario, London, 2011.
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.
Chen C and Maza M M, Algorithms for computing triangular decomposition of polynomial systems, J. Symb. Comput., 2012, 47(6): 610–642.
Buchberger B, Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal, PhD thesis, Universitat Insbruck, 1965.
Hashemi A and Lazard D, Complexity of zero-dimensional gröbner bases, PhD thesis, INRIA, 2005.
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.
Faugere J C, A new efficient algorithm for computing gröbner bases (f4), J. Pure Appl. Algebra, 1999, 139(1–3): 61–88.
Faugere J C, A new efficient algorithm for computing gröbner bases without reduction to zero (f5), Proc. ISSAC’02, 2002, 75–83.
Lazard D, Solving zero-dimensional algebraic systems, J. Symb. Comput., 1992, 13(2): 117–131.
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.
Wang D, On the connection between ritt characteristic sets and buchberger-gröbner bases, Math. Comput. Sci., 2016, 10(4): 479–492.
Becker T and Weispfenning V, Gröbner Bases, Springer, New York, 1998.
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.
Cox D A, Little J B, and OShea D, Using Algebraic Geometry, Graduate texts in mathematics, 2nd Edition, Springer Science & Business Media, 2005.
Boulier F, Lemaire F, and Maza M M, Well known theorems on triangular systems and the d5 principle, TC, 2006, 79–91.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
The authors declare no conflict of interest.
Additional information
This research was supported by National Key R&D Program of China (No. 2022YFA1005102) and the National Natural Science Foundation of China under Grant No. 61732001.
Rights and permissions
About this article
Cite this article
Li, H., Xia, B. & Zhao, T. Square-Free Pure Triangular Decomposition of Zero-Dimensional Polynomial Systems. J Syst Sci Complex 36, 2661–2680 (2023). https://doi.org/10.1007/s11424-023-2260-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-023-2260-3