×

Multiplicity-preserving triangular set decomposition of two polynomials. (English) Zbl 1317.12002

Summary: In this paper, a multiplicity-preserving triangular set decomposition algorithm is proposed for a system of two polynomials, which involves only computing the primitive polynomial remainder sequence of two polynomials once and certain GCD computations. The algorithm decomposes the unmixed variety defined by two polynomials into square free and disjoint (for non-vertical components, see Definition 4) algebraic cycles represented by triangular sets, which may have negative multiplicities. Thus, the authors can count the multiplicities of the non-vertical components. In the bivariate case, the authors give a complete algorithm to decompose the system into zeros represented by triangular sets with multiplicities. The authors also analyze the complexity of the algorithm in the bivariate case. The authors implement the algorithm and show the effectiveness of the method with extensive experiments.

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Software:

Epsilon
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ritt J, Differential Algebra, New York, Dover Publications, 1966.
[2] Wu W T, Basic principles of mechanical theorem-proving in elementary geometries, Journal Automated Reasoning, 1986, 2: 221-252. · Zbl 0642.68163
[3] Wu W T, Basic Principle of Mechanical Theorem Proving in Geometries, Science Press, Beijing, 1984; Springer, Wien, 1994 (in Chinese).
[4] Aubry P, Lazard D, and Moreno Maza M, On the theories of triangular sets, J. Symb. Comput., 1999, 28(1-2): 105-124. · Zbl 0943.12003
[5] Chen, C.; Golubitsky, O.; Lemaire, F.; Moreno Maza, M.; Pan, W., Comprehensive triangular decomposition, 73-101 (2007) · Zbl 1141.68677
[6] Chou S C and Gao X S, Ritt-Wu’s decomposition algorithm and geometry theorem proving, CADE’10, ed. by Stickel M E, Lecture Notes in Computer Science, Springer-Verlag, 1990, 449: 207-220. · Zbl 0708.68062
[7] Dahan, X.; Moreno Maza, M.; Schost; Wu, W.; Xie, Y., Lifting techniques for triangular decompositions (2005) · Zbl 1360.14146
[8] Gao X S and Chou S C, On the dimension of an arbitrary ascending chain, Chinese Sci. Bull., 1993, 38: 799-804. · Zbl 0845.13004
[9] Gerdt V P and Blinkov Y A, Involutive bases of polynomial ideals, Mathematics and Computers in Simulation, 1998, 45(5-6): 519-541. · Zbl 1017.13500
[10] Golubitsky O, Kondratieva M, Ovchinnikov A, and Szanto A, A bound for orders in differential Nullstellensatz. Journal of Algebra, 2009, 322: 3852-3877. · Zbl 1189.12002
[11] Hubert, E., No article title, Notes on triangular sets and triangulation-decomposition algorithms I: Polynomial systems, 2630, 1-39 (2003)
[12] Lazard D, A new method for solving algebraic systems of positive dimension, Discrete Appl. Math., 1991, 33: 147-160. · Zbl 0753.13013
[13] Li, X.; Moreno Maza, M.; Schost, Fast arithmetic for triangular sets: From theory to practice, 269-276 (2007) · Zbl 1190.68093
[14] Moreno Maza, M., On triangular decompositions of algebraic varieties (2000)
[15] Kalkbrener M, A generalized euclidean algorithm for computing triangular representations of algebraic varieties, J. Symb. Comput., 1993, 15(2): 143-167. · Zbl 0783.14039
[16] Kalkbrener M, Primitive polynomial remainder sequence in elimination theory, Applicable Algebra in Engineering, Communication and Computing, 1995, 6: 65-79. · Zbl 0845.12006
[17] Kalkbrener M, Algorithmic properties of polynomial rings, J. Symb. Comput., 1998, 26(5): 525-581. · Zbl 0920.68129
[18] Wang D, Computing triangular systems and regular systems, J. Symb. Comput., 2000, 30(2): 221-236. · Zbl 1007.65039
[19] Wu W T, On a linear equations method of non-linear polynomial equations-solving, Systems Science and Mathematical Sciences, 1993, 6(1): 1-12. · Zbl 0794.65045
[20] Yang, L.; Zhang, J., Searching dependency between algebraic equations: An algorithm applied to automated reasoning, 147-156 (1994) · Zbl 0808.68069
[21] Lazard D, Solving zero-dimensional algebraic systems, J. Symb. Comput., 1992, 13: 117-131. · Zbl 0753.13012
[22] Li B H, A method to solve algebraic equations up to multiplicities via Ritt-Wu’s characteristic sets, Acta Analysis Functionalis Applicata, 2003, 5(3): 98-109. · Zbl 1030.65055
[23] Li, Y.; Xia, B.; Zhang, Z., Zero decomposition with multiplicity of zero-dimensional polynomial systems (in Chinese), 19-22 (2010)
[24] Bates D, Peterson C, and Sommese A J, A numerical-symbolic algorithm for computing the multiplicity of a component of an algebraic set, Journal of Complexity, 2006, 22(4): 475-489. · Zbl 1100.65046
[25] Dayton, B.; Zeng, Z., Computing the multiplicity structure in solving polynomial systems (2005) · Zbl 1360.65151
[26] Lazard D, Ideal bases and primary decomposition: Case of two variables, J. Symb. Comput., 1985, 1: 261-270. · Zbl 0616.68036
[27] Brown W S, The subresultant PRS algorithm, ACM Trans. on Mathematical Software, 1978, 4: 237-249. · Zbl 0385.68044
[28] Hodge W V D and Pedoe D, Methods of Algebraic Geometry, Volume II, University Press Cambridge, ISBN 0 521 46901 5 paperback, 1994. · Zbl 0796.14003
[29] Gel’fand I M, Kapranov M, and Zelevinsky A. Discriminants, Resultants and Multidimensional Determinants, Boston, Birkhäuser, 1994. · Zbl 0827.14036
[30] Cox D A, Little J, and O’Shea D, Using Algebraic Geometry, Springer, Second Edition, 2004.
[31] Hodge W V D and Pedoe D, Methods of algebraic geometry, Volume I, University Press Cambridge, ISBN 0 521 469007 4 paperback, 1994. · Zbl 0796.14003
[32] Macaulay F S, The Algebraic Theory of Modular Systems, Cambridge University Press, 1916, reprint 1994. · JFM 46.0167.01
[33] Fulton W, Algebraic Curves, The third version, online, 2008.
[34] Boulier, F.; Lemaire, F.; Moreno Maza, M., Well known theorems on triangular systems and the D5 principle (2006) · Zbl 1213.13044
[35] Dora, J. D.; Discrescenzo, C.; Duval, D., No article title, About a new method method for computing in algebraic number fields, 204, 289-290 (1985)
[36] Sun Y and Wang D K, An efficient algorithm for factoring polynomials over algebraic extension field, arXiv:0907.2300v2 [cs.SC]. · Zbl 1271.12007
[37] Diochnos D I, Emiris I Z, and Tsigaridas E P, On the asymptotic and practical complexity of solving bivariate systems over the reals, J. Symb. Comput., 2009, 44: 818-835. · Zbl 1169.13306
[38] Reischert, D., Asymptotically fast computation of subresultants, 233-240 (1997) · Zbl 0928.68145
[39] Wang D, Elimination Practice, Software Tools, and Applications, Imperial College Press, 2004. · Zbl 1099.13047
[40] Wang, D. K., Zero decomposition for system of polynomial equations, 67-70 (2000) · Zbl 0981.65063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.