Complexity of irreducibility testing for a system of linear ordinary differential equations

ABSTRACT

Let a system of linear ordinary differential equations of the first order Y′ = AY be given, where A is n × n matrix over a field F(X), assume that the degree degX(A) < d and the size of any coefficient occurring in A is at most M. The system Y′ = AY is called reducible if it is equivalent (over the field F(X)) to a system Y&prime1 = A1Y1 with a matrix A1 of the form A1 = (A1,1 0) (A2,1 A2,2) An algorithm is described for testing irreducibility of the system with the running time exp(M(d2n)d2n).

REFERENCES

• BBH 88: Beukers, F., Brownawell, D. and Heckman, G., Siegel Normality, Ann. Math. 127 (1988), pp. 279-308.
• CG 83: Chistov, A. L. and Grigoriev, D. Yu., Subezponential-lime Solving $ysiems of Algebraic Equations, volumes i and II (1983), Preprints LOMI E-9-83 and E-10-83, Leningrad.
• CL 55: Coddington, E. and Levinson, N., Theory of Ordinary Differeniial Equations, McGraw- Hill, New York (1955).
• Gr 86: Grigoriev, D. 'flu., Computational Complexity in Polynomial Algebra, Proceedings of the International Congress of Mathematicians, volume 2, Berkeley (1986), pp. 1452- 1460.
• Gr 90: 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]
• Ka 57: Kaplanski, I., An Introduction to Differential Algebra, Hermann, Paris (1957).
• La 65: Lang, S., Algebra, Addison-Wesley, Reading (1905).
• Si 81: Singer, M., Liouvillean Solutions of n-th Order Homogeneous Linear Differential Equations, Amer. J. Math. 103 (1981), pp. 661- 682.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

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

General Terms:
Algorithms