An improved algorithm for factoring linear ordinary differential operators

ABSTRACT

We describe an efficient algorithm for computing the associated equations appearing in the Beke-Schlesinger factorisation method for linear ordinary differential operators. This algorithm, which is based on elementary operations with sets of integers, can be easily implemented for operators of any order, produces several possible associated equations, of which only the simplest can be selected for solving, and often avoids the degenerate case, where the order of the associated equation is less than in the generic case. We conclude with some fast heuristics that can produce some factorisations while using only linear computations.

REFERENCES

• 1: S. A. Abramov , K. Yu. Kvansenko, Fast algorithms to search for the rational solutions of linear differential equations with polynomial coefficients, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.267-270, July 15-17, 1991, Bonn, West Germany [doi>10.1145/120694.120735]
• 2: M. A. Barkatou (1993): An Algorithm for Computing a Companion Block Diagonal Form for a System of Linear Differential Equations, Apphcable Algebra ,n Engineering, Communication and Computing 4~ 185-195.
• 3: E. Beke (1894): Die irreduzibilit~t der homogenen linearen Differentialgleichungen, Math. Ann. 45~ 278-294.
• 4: Manuel Bronstein, On solutions of linear ordinary differential equations in their coefficient field, Journal of Symbolic Computation, v.13 n.4, p.413-439, April 1992 [doi>10.1016/S0747-7171(08)80106-X]
• 5: Manuel Bronstein, Linear ordinary differential equations: breaking through the order 2 barrier, Papers from the international symposium on Symbolic and algebraic computation, p.42-48, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143264]
• 6: M. Bronstein & M. Petkov~ek (1994): On Ore rings, linear operators and factorisation, Programmirovanie 1~ 27-45. Also Research Report 200, Informatik, ETH Ziirich.
• 7: L. Schlesinger (1895): Handbuch der Theorie der linearen Differentialgleichungen, Teubner, Leipzig.
• 8: 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]
• 9: Michael F. Singer, Liouvillian solutions of linear differential equations with Liouvillian coefficients, Journal of Symbolic Computation, v.11 n.3, p.251-273, March 1991 [doi>10.1016/S0747-7171(08)80048-X]
• 10: Michael F. Singer , Felix Ulmer, Liouvillian and algebraic solutions of second and third order linear differential equations, Journal of Symbolic Computation, v.16 n.1, p.37-73, July 1993 [doi>10.1006/jsco.1993.1033]
• 11: 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]
• 12: K. Wolf (1992): Zff~ziente Algorithmen zur Lb'sung linearer Differentialgleichungsysteme und zur Faktorisierung linearer Differentialoperatoren iiber liouvillischen Kb'rpern, Doctoral dissertation, Mathematics, RFW Universit~t, Bonn.
• 13: B. Ziircher (1994): Rationale Normalform yon pseudolinearen Abbildungen, Diplomarbeit, Mathematics, ETH Zfirich.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory, Verification