Decomposition of differential polynomials with constant coefficients

ABSTRACT

In this paper, we present an algorithm to decompose differential polynomials in one variable and with rational number as coefficients. Besides arithmetic operations, the algorithm needs only factorization of multi-variable polynomials and solution of linear equation systems. Experimental results show that our method is quite efficient.

REFERENCES

• 1: Vangalur S. Alagar , Mai Tanh, Fast Polynominal Decomposition Algorithms, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.150-153, April 01-03, 1985
• 2: M. A. Barkatou , E. Pflügel, On the equivalence problem of linear differential systems and its application for factoring completely reducible systems, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.268-275, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281633]
• 3: D R Barton , R Zippel, Polynomial decomposition algorithms, Journal of Symbolic Computation, v.1 n.2, p.159-168, June 1985 [doi>10.1006/jsco.1994.1009]
• 4: Manuel Bronstein, An improved algorithm for factoring linear ordinary differential operators, Proceedings of the international symposium on Symbolic and algebraic computation, p.336-340, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190436]
• 5: M. Bronstein and M. Petkovsek. On Ore rings, linear operators and factorization. Programming & Computer Software 20, 1, 27--44, 1994.
• 6: Thomas Cluzeau, Factorization of differential systems in characteristic p, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.58-65, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860875]
• 7: Anne Fredet, Factorization of linear differential operators in exponential extensions, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.103-110, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860885]
• 8: X.S. Gao and M. Zhang. Decomposition of differential polynomials. In MM Res. Preprints, No. 22, 163--185, 2003. http://www.mmrc.iss.ac.cn/pub/mm-pre.html
• 9: J. von zur Gathen, Functional decomposition of polynomials: the Tame case, Journal of Symbolic Computation, v.9 n.3, p.281-299, March 1990 [doi>10.1016/S0747-7171(08)80014-4]
• 10: Mark Giesbrecht , Yang Zhang, Factoring and decomposing ore polynomials over F_q(t), Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.127-134, August 03-06, 2003, Philadelphia, PA, USA [doi>10.1145/860854.860888]
• 11: D. Yu. Grigor'ev, Complexity of factoring and calculating the GCD of linear ordinary differential operators, Journal of Symbolic Computation, v.10 n.1, p.7-37, July 1990 [doi>10.1016/S0747-7171(08)80034-X]
• 12: Jaime Gutierrez , Tomás Recio , C. Ruiz de Velasco, Polynomial Decomposition Algorithm of Almost Quadratic Complexity, Proceedings of the 6th International Conference, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.471-475, July 04-08, 1988
• 13: Ziming Li , Fritz Schwarz , Serguei P. Tsarev, Factoring systems of linear PDEs with finite-dimensional solution spaces, Journal of Symbolic Computation, v.36 n.3-4, p.443-471, September 2003 [doi>10.1016/S0747-7171(03)00090-7]
• 14: E.R. Kolchin. Differential Algebra and Algebraic Groups, Academic Press, London, 1973.
• 15: L. Konigsberger. Allgemeine Untersuchungen aus der Theorie der Differentialgleichungen, Teubner, Leipzig, 1882.
• 16: Dexter Kozen , Susan Landau, Polymonial decomposition algorithms, Journal of Symbolic Computation, v.7 n.5, p.445-456, May 1989 [doi>10.1016/S0747-7171(89)80027-6]
• 17: J.F. Ritt. Prime and composite pols. Trans. AMS, 23, 51--66, 1922.
• 18: F. Schwarz, A factorization algorithm for linear ordinary differential equations, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.17-25, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74544]
• 19: M.F. Singer. Liouillian solutions of nth order homogeneous linear differential equations. Amer. J. of Math., 103(4), 661--682, 1981.
• 20: O. Ore. Theory of non-commutative polynomials. The Annals of Mathematics, 34(3), 480--508, 1933.
• 21: Michael F. Singer , Felix Ulmer, Galois groups of second and third order linear differential equations, Journal of Symbolic Computation, v.16 n.1, p.9-36, July 1993 [doi>10.1006/jsco.1993.1032]
• 22: M. Sosnin. Decomposition of polynomial ordinary differential equations. Krasnoyarsk, to be published, 1999.
• 23: S. P. Tsarev, An algorithm for complete enumeration of all factorizations of a linear ordinary differential operator, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.226-231, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.237079]
• 24: S. P. Tsarev, On factorization of nonlinear ordinary differential equations, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.159-164, July 28-31, 1999, Vancouver, British Columbia, Canada [doi>10.1145/309831.309899]
• 25: H. Umemura. On the irreducibility of the first differential equation of Painleve. In Algebraic geometry and commutative algebra in honor of Masayoshi Nagata, Tokyo, 101--109, 1987.
• 26: Mark Van Hoeij, Factorization of differential operators with rational functions coefficients, Journal of Symbolic Computation, v.24 n.5, p.537-561, Nov. 1997 [doi>10.1006/jsco.1997.0151]
• 27: Mark Van Hoeij, Formal solutions and factorization of differential operators with power series coefficients, Journal of Symbolic Computation, v.24 n.1, p.1-30, July 1997 [doi>10.1006/jsco.1997.0110]
• 28: M. Van der Put and M.F. Singer. Galois theory of linear differential equations, Springer, Berlin, 2003.
• 29: Richard Zippel, Rational function decomposition, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.1-6, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120695]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms

Keywords:
decomposition, differential degree, differential polynomial, pseudo linear