Abstract
An algorithm for computation of an extended characteristic sets for finitely generated differential ideals is suggested. This algorithm improves the well-known Kolchin–Ritt algorithm. The improvement is achieved through computing algebraic Gröbner bases on intermediate stages of the computation process. The rank of the extended characteristic set obtained is less than or equal to that of the set obtained by the Kolchin–Ritt algorithm. Examples demonstrating the rank reduction are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.REFERENCES
Ritt, J.F., Differential Algebra, New York: AMS, 1950.
Kolchin, E.R., Differential Algebra and Algebraic Groups, New York: Academic, 1973.
Wu, W.-T., On the Foundation of Algebraic Differential Geometry, System Sci. Math. Sci., 1989, vol. 2, pp. 289–312.
Boulier, F., Lazard, D., Ollivier, F., and Petitot, M., Representation for the Radical of a Finitely Generated Differential Ideal, Proc. of ISSAC'95, ACM, 1995, pp. 158–166.
Mansfield, E. and Clarkson, P.A., Application of the Differential Algebra Package diffgrob2 to Classical Symmetries of Differential Equations, J. Symb. Comp., 1997, vol. 23, pp. 517–533.
Boulier, F., Lazard, D., Ollivier, F., and Petitot, M., Computing Representations for Radicals of Finitely Generated Differential Ideals, Tech. Report, LIFL, Université Lille I, 1997.
Rosenfeld, A., Specializations in Differential Algebra, Trans. Am. Math. Soc., 1959, vol. 90, pp. 394–407.
Buchberger, B., Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory, Recent Trends in Multidimensional System Theory, Bose, N.K., Ed., Dordrecht: Reidel, 1985, pp. 184–232. Translated under the title Komp'yuternaya algebra. Simvol'nye i algebraicheskie vychisleniya, Moscow: Mir, 1986, pp. 331–372.
Mikhalev, A.V. and Pankrat'ev, E.V., Computer Algebra. Computation in Differential and Difference Algebra, Moscow: Mosk. Gos. Univ., 1989.
Hubert, E., Factorization-free Decomposition Algorithms in Differential Algebra, J. Symb. Comp., 2000, vol. 29, pp. 641–662.
Knuth, D.E., The Art of Computer Programming, vol. 2: Seminumerical Algorithms, Reading: Addison-Wesley, 1969. Translated under the title Iskusstvo programmirovaniya dlya EVM, tom 2: Poluchislennye algoritmy Moscow: Mir, 1977.
Carra'Ferro, G., Gröbner Bases and Differential Algebra, Lecture Notes in Computer Science, 1987, vol. 356, pp. 129–140.
Ollivier, F., Standard Bases of Differential Ideals, Lecture Notes in Computer Science, 1990, vol. 508, pp. 304–321.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Carra'Ferro, G., Gerdt, V.P. Improved Kolchin–Ritt Algorithm. Programming and Computer Software 29, 83–87 (2003). https://doi.org/10.1023/A:1022996615890
Issue Date:
DOI: https://doi.org/10.1023/A:1022996615890