Abstract
In this paper, a new triangular decomposition algorithm is proposed for ordinary differential polynomial systems, which has triple exponential computational complexity. The key idea is to eliminate one algebraic variable from a set of polynomials in one step using the theory of multivariate resultant. This seems to be the first differential triangular decomposition algorithm with elementary computation complexity.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ritt J F, Differential Algebra, American Mathematical Society, Colloquium Publications, Vol. 33, 1950.
Wu W T, Basic Principle of Mechanical Theorem Proving in Geometries, Science Press, Beijing, 1984. English translation, Springer, Wien, 1994.
Aubry P, Lazard D, and Maza M M, On the theories of triangular sets, J. Symb. Comput., 1999, 28: 105–124.
Szanto A, Computation with Polynomial Systems, Doctoral Dissertation, Cornell University, 1999.
Wang D, An elimination method for polynomial systems, J. Symb. Comput., 1993, 16: 83–114.
Boulier F, Lazard D, Ollivier F, et al., Representation for the radical of a finitely generated differential ideal, Proc. of ISSAC’95, ACM Press, 1995, 158–166.
Bouziane D, Kandri Rody A, and Maârouf H, Unmixed-dimensional decomposition of a finitely generated perfect differential ideal, J. Symb. Comput., 2001, 31: 631–649.
Chou S C and Gao X S, Automated reasoning in differential geometry and mechanics using the characteristic set method, Part I. An improved version of Ritt-Wu’s decomposition algorithm, Journal of Automated Reasoning, 1993, 10: 161–172.
Hubert E, Factorization-free decomposition algorithms in differetntial algebra, J. Symb. Comput., 2000, 29(4–5): 641–662.
Wu WT, A constructive theorey of differential algebraic geometry, Lect. Notes in Math., Springer, 1987, 1255: 173–189.
Cheng J S and Gao X S, Multiplicity-preserving triangular set decomposition of two polynomials, Journal of Systems Science and Complexity, 2014, 27(6): 1320–1344.
Gao X S, Luo Y, and Yuan C, A characteristic set method for difference polynomial systems, J. Symb. Comput., 2009, 44(3): 242–260.
Gao X S and Huang Z, Characteristic set algorithms for equation solving in finite fields, J. Symb. Comput., 2012, 47: 655–679.
Huang Z, Parametric equation solving and qiantifier elimination in finite fields with characteristic set method, Journal of Systems Science and Complexity, 2012, 25(4): 778–791.
Li X, Mou C, and Wang D, Decomposing polynomial sets into somple sets over finite fields: The zero-dimensional case, Computer and Mathematics with Applications, 2010, 60: 2983–2997.
Chen C, Davenport J H, May J P, et al., Triangular decomposition of semi-algebraic systems, Proc. ISSAC 2010, ACM Press, New York, 2010, 187–194.
Gallo G and Mishra B, Efficient algorithms and bounds for Wu-Ritt characteristic sets, Progress in Mathematics, 1991, 94: 119–142.
Golubitsky O, Kondratieva M, Ovchinnikov A, et al., A bound for orders in differential nullstellensatz, Journal of Algebra, 2009, 322(11): 3852–3877.
Grigor’ev D Y, Complexity of quantifier elimination in the theory of ordinary differential equations, Lecture Notes in Computer Science, 1984, 176: 17–31.
Gao X S and Chou C, On the dimension of an arbitrary ascending chain, Chinese Sci. Bull., 1993, 38: 799–804.
Hartshorne R, Algebraic Geometry, Springer-Verlag, Berlin, 1977.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by the National Natural Science Foundation of China under Grant No. 60821002 and the National Key Basic Research Project of China.
This paper was recommended for publication by Editor LI Hongbo.
Rights and permissions
About this article
Cite this article
Zhu, W., Gao, XS. A triangular decomposition algorithm for differential polynomial systems with elementary computation complexity. J Syst Sci Complex 30, 464–483 (2017). https://doi.org/10.1007/s11424-016-5040-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-016-5040-5