Decomposition of polynomial sets into characteristic pairs

Wang, Dongming; Dong, Rina; Mou, Chenqi

doi:10.1090/mcom/3504

Decomposition of polynomial sets into characteristic pairs
HTML articles powered by AMS MathViewer

by Dongming Wang, Rina Dong and Chenqi Mou;

Math. Comp. 89 (2020), 1993-2015

DOI: https://doi.org/10.1090/mcom/3504

Published electronically: January 7, 2020

HTML | PDF | Request permission

Uncorrected version: Original version posted January 7, 2020
Corrected version: This version of the article replaces an earlier version, due to a publisher error

Abstract:

A characteristic pair is a pair $(\mathcal {G}, \mathcal {C})$ of polynomial sets in which $\mathcal {G}$ is a reduced lexicographic Gröbner basis and $\mathcal {C}$ is the minimal triangular set contained in $\mathcal {G}$. It is said to be normal (or strong normal) if $\mathcal {C}$ is normal (or $\mathcal {C}$ is normal and its saturated ideal equals the ideal generated by $\mathcal {G}$). In this paper, we show that any finite polynomial set $\mathcal {P}$ can be decomposed algorithmically into finitely many (strong) normal characteristic pairs with associated zero relations, which provide representations for the zero set of $\mathcal {P}$ in terms of those of Gröbner bases and those of triangular sets. The algorithm we propose for the decomposition makes use of the inherent connection between Ritt characteristic sets and lexicographic Gröbner bases and is based essentially on the structural properties and the computation of lexicographic Gröbner bases. Several nice properties about the decomposition and the resulting (strong) normal characteristic pairs, in particular relationships between the Gröbner basis and the triangular set in each pair, are established. Examples are given to illustrate the algorithm and some of the properties.

References

Gerhard Angermüller, Triangular systems and a generalization of primitive polynomials. part 1, J. Symbolic Comput. 68 (2015), no. part 1, 316–325. MR 3283849, DOI 10.1016/j.jsc.2014.09.022
P. Aubry, Ensembles triangulaires de polynômes et résolution de systemes algébriques. implantation en axiom, Ph.D. thesis, Université Pierre et Marie Curie, France, 1999.
Philippe Aubry, Daniel Lazard, and Marc Moreno Maza, On the theories of triangular sets, J. Symbolic Comput. 28 (1999), no. 1-2, 105–124. Polynomial elimination—algorithms and applications. MR 1709419, DOI 10.1006/jsco.1999.0269
Philippe Aubry and Marc Moreno Maza, Triangular sets for solving polynomial systems: a comparative implementation of four methods, J. Symbolic Comput. 28 (1999), no. 1-2, 125–154. Polynomial elimination—algorithms and applications. MR 1709420, DOI 10.1006/jsco.1999.0270
Thomas Bächler, Vladimir Gerdt, Markus Lange-Hegermann, and Daniel Robertz, Algorithmic Thomas decomposition of algebraic and differential systems, J. Symbolic Comput. 47 (2012), no. 10, 1233–1266. MR 2926124, DOI 10.1016/j.jsc.2011.12.043
B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal, Ph.D. thesis, Universität Innsbruck, Austria, 1965.
B. Buchberger, Gröbner bases: An algorithmic method in polynomial ideal theory, Multidimensional Systems Theory (Nirmal Bose, ed.), Springer, Netherlands, 1985, pp. 184–232.
C. Chen, O. Golubitsky, F. Lemaire, M. Moreno Maza, and W. Pan, Comprehensive Triangular Decomposition, Proceedings of CASC 2007 (Victor Ganzha, Ernst Mayr, and Evgenii Vorozhtsov, eds.), Springer-Verlag, Berlin Heidelberg, 2007, pp. 73–101.
Changbo Chen and Marc Moreno Maza, Algorithms for computing triangular decomposition of polynomial systems, J. Symbolic Comput. 47 (2012), no. 6, 610–642. MR 2908585, DOI 10.1016/j.jsc.2011.12.023
Shang-Ching Chou and Xiao Shan Gao, Ritt-Wu’s decomposition algorithm and geometry theorem proving, 10th International Conference on Automated Deduction (Kaiserslautern, 1990) Lecture Notes in Comput. Sci., vol. 449, Springer, Berlin, 1990, pp. 207–220. MR 1077003, DOI 10.1007/3-540-52885-7_{8}9
S. Collart, M. Kalkbrener, and D. Mall, Converting bases with the Gröbner walk, J. Symbolic Comput. 24 (1997), no. 3-4, 465–469. Computational algebra and number theory (London, 1993). MR 1484492, DOI 10.1006/jsco.1996.0145
David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, 3rd ed., Undergraduate Texts in Mathematics, Springer, New York, 2007. An introduction to computational algebraic geometry and commutative algebra. MR 2290010, DOI 10.1007/978-0-387-35651-8
X. Dahan, On lexicographic Gröbner bases of radical ideals in dimension zero: Interpolation and structure, Preprint at arXiv:1207.3887, 2012.
J. D. Dora, C. Dicrescenzo, and D. Duval, About a new method for computing in algebraic number fields, Proceedings of EUROCAL ’85 (Bruno Buchberger, ed.), Springer-Verlag, Berlin Heidelberg, 1985, pp. 289–290.
Stéphane Dellière, On the links between triangular sets and dynamic constructible closure, J. Pure Appl. Algebra 163 (2001), no. 1, 49–68. MR 1847375, DOI 10.1016/S0022-4049(00)00136-5
Jean-Charles Faugére, A new efficient algorithm for computing Gröbner bases $(F_4)$, J. Pure Appl. Algebra 139 (1999), no. 1-3, 61–88. Effective methods in algebraic geometry (Saint-Malo, 1998). MR 1700538, DOI 10.1016/S0022-4049(99)00005-5
J. C. Faugére, A New Efficient Algorithm for Computing Gröbner Bases Without Reduction to Zero (${F_5}$), Proceedings of ISSAC 2002 (Teo Mora, ed.), ACM Press, 2002, pp. 75–83.
J. C. Faugère, P. Gianni, D. Lazard, and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symbolic Comput. 16 (1993), no. 4, 329–344. MR 1263871, DOI 10.1006/jsco.1993.1051
Shuhong Gao, Frank Volny IV, and Mingsheng Wang, A new framework for computing Gröbner bases, Math. Comp. 85 (2016), no. 297, 449–465. MR 3404457, DOI 10.1090/mcom/2969
X.-S. Gao and S.-C. Chou, Solving Parametric Algebraic Systems, Proceedings of ISSAC 1992 (Paul Wang, ed.), ACM Press, 1992, pp. 335–341.
X.-S. Gao and S.-C. Chou, On the dimension of an arbitrary ascending chain, Chinese Science Bulletin - English Edition 38 (1993), 799–799.
Patrizia Gianni, Properties of Gröbner bases under specializations, EUROCAL ’87 (Leipzig, 1987) Lecture Notes in Comput. Sci., vol. 378, Springer, Berlin, 1989, pp. 293–297. MR 1033305, DOI 10.1007/3-540-51517-8_{1}28
Patrizia Gianni, Barry Trager, and Gail Zacharias, Gröbner bases and primary decomposition of polynomial ideals, J. Symbolic Comput. 6 (1988), no. 2-3, 149–167. Computational aspects of commutative algebra. MR 988410, DOI 10.1016/S0747-7171(88)80040-3
Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Regeneration homotopies for solving systems of polynomials, Math. Comp. 80 (2011), no. 273, 345–377. MR 2728983, DOI 10.1090/S0025-5718-2010-02399-3
Evelyne Hubert, Notes on triangular sets and triangulation-decomposition algorithms. I. Polynomial systems, Symbolic and numerical scientific computation (Hagenberg, 2001) Lecture Notes in Comput. Sci., vol. 2630, Springer, Berlin, 2003, pp. 1–39. MR 2043699, DOI 10.1007/3-540-45084-X_{1}
Michael Kalkbrener, Solving systems of algebraic equations by using Gröbner bases, EUROCAL ’87 (Leipzig, 1987) Lecture Notes in Comput. Sci., vol. 378, Springer, Berlin, 1989, pp. 282–292. MR 1033304, DOI 10.1007/3-540-51517-8_{1}27
Michael Kalkbrener, A generalized Euclidean algorithm for computing triangular representations of algebraic varieties, J. Symbolic Comput. 15 (1993), no. 2, 143–167. MR 1218756, DOI 10.1006/jsco.1993.1011
Deepak Kapur, Yao Sun, and Dingkang Wang, A new algorithm for computing comprehensive Gröbner systems, ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2010, pp. 29–36. MR 2920533, DOI 10.1145/1837934.1837946
D. Lazard, Ideal bases and primary decomposition: case of two variables, J. Symbolic Comput. 1 (1985), no. 3, 261–270. MR 849035, DOI 10.1016/S0747-7171(85)80035-3
D. Lazard, A new method for solving algebraic systems of positive dimension, Discrete Appl. Math. 33 (1991), no. 1-3, 147–160. Applied algebra, algebraic algorithms, and error-correcting codes (Toulouse, 1989). MR 1137743, DOI 10.1016/0166-218X(91)90113-B
D. Lazard, Solving zero-dimensional algebraic systems, J. Symbolic Comput. 13 (1992), no. 2, 117–131. MR 1153638, DOI 10.1016/S0747-7171(08)80086-7
François Lemaire, Marc Moreno Maza, Wei Pan, and Yuzhen Xie, When does $\langle T\rangle$ equal $\textrm {sat}(T)$?, J. Symbolic Comput. 46 (2011), no. 12, 1291–1305. MR 2860999, DOI 10.1016/j.jsc.2011.08.010
B. Li and D. Wang, An Algorithm for Transforming Regular Chain into Normal Chain, Computer Mathematics (Deepak Kapur, ed.), Springer-Verlag, Berlin Heidelberg, 2008, pp. 236–245.
Maria Grazia Marinari and Teo Mora, A remark on a remark by Macaulay or enhancing Lazard structural theorem, Bull. Iranian Math. Soc. 29 (2003), no. 1, 1–45, 85 (English, with Persian summary). MR 2046304
Chenqi Mou, Dongming Wang, and Xiaoliang Li, Decomposing polynomial sets into simple sets over finite fields: the positive-dimensional case, Theoret. Comput. Sci. 468 (2013), 102–113. MR 3003772, DOI 10.1016/j.tcs.2012.11.009
Adrien Poteaux and Éric Schost, On the complexity of computing with zero-dimensional triangular sets, J. Symbolic Comput. 50 (2013), 110–138. MR 2996871, DOI 10.1016/j.jsc.2012.05.008
Joseph Fels Ritt, Differential Algebra, American Mathematical Society Colloquium Publications, Vol. XXXIII, American Mathematical Society, New York, 1950. MR 35763
Takeshi Shimoyama and Kazuhiro Yokoyama, Localization and primary decomposition of polynomial ideals, J. Symbolic Comput. 22 (1996), no. 3, 247–277. MR 1427183, DOI 10.1006/jsco.1996.0052
Ding-kang Wang and Yan Zhang, An algorithm for decomposing a polynomial system into normal ascending sets, Sci. China Ser. A 50 (2007), no. 10, 1441–1450. MR 2390461, DOI 10.1007/s11425-007-0118-0
Dong Ming Wang, An elimination method for polynomial systems, J. Symbolic Comput. 16 (1993), no. 2, 83–114. MR 1253907, DOI 10.1006/jsco.1993.1035
Dongming Wang, Decomposing polynomial systems into simple systems, J. Symbolic Comput. 25 (1998), no. 3, 295–314. MR 1615318, DOI 10.1006/jsco.1997.0177
Dongming Wang, Computing triangular systems and regular systems, J. Symbolic Comput. 30 (2000), no. 2, 221–236. MR 1777174, DOI 10.1006/jsco.1999.0355
D. Wang, Elimination Methods, Springer-Verlag, Wien, 2001.
Dongming Wang, Epsilon: a library of software tools for polynomial elimination, Mathematical software (Beijing, 2002) World Sci. Publ., River Edge, NJ, 2002, pp. 379–389. MR 1932623
Dongming Wang, Elimination practice, Imperial College Press, London, 2004. Software tools and applications; With 1 CD-ROM (UNIX/LINUX, Windows). MR 2050441, DOI 10.1142/9781848161207
Dongming Wang, On the connection between Ritt characteristic sets and Buchberger-Gröbner bases, Math. Comput. Sci. 10 (2016), no. 4, 479–492. MR 3569681, DOI 10.1007/s11786-016-0279-8
Volker Weispfenning, Comprehensive Gröbner bases, J. Symbolic Comput. 14 (1992), no. 1, 1–29. MR 1177987, DOI 10.1016/0747-7171(92)90023-W
Wen Jun Wu, On zeros of algebraic equations—an application of Ritt principle, Kexue Tongbao (English Ed.) 31 (1986), no. 1, 1–5. MR 850170
Wen Tsün Wu, Mechanical theorem proving in geometries, Texts and Monographs in Symbolic Computation, Springer-Verlag, Vienna, 1994. Basic principles; Translated from the 1984 Chinese original by Xiao Fan Jin and Dong Ming Wang. MR 1284925, DOI 10.1007/978-3-7091-6639-0
Wen-Tsun Wu, Mathematics mechanization, Mathematics and its Applications, vol. 489, Kluwer Academic Publishers Group, Dordrecht; Science Press Beijing, Beijing, 2000. Mechanical geometry theorem-proving, mechanical geometry problem-solving and polynomial equations-solving. MR 1834540