Efficient factorization of linear ODE's

ABSTRACT

Factorization and testing for irreducibility has turned out to be one of the most important algorithms for handling linear ode's. The main hindrance for applying it is its tremendeous complexity originating to a large extent from solving certain Riccati equations which occur during the factorization. The solution procedure for these Riccati equations is much more manageable if it is subdivided into two major parts. At first so called solution candidates are determined each of which depends only on the parameters of a single irreducible denominator or the behavior at infinity. In a second step it is tried to complete each candidate into a genuine solution of the Riccati equation, possibly including an unspecified number of additional first order poles. Furthermore a scheme is proposed for running the factorization procedure in parallel on a two-processor machine in which possible factors are searched for both from the right and the left at the same time.

REFERENCES

• 1: 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]
• 2: G. Frobenius, <i>&Uuml;ber den Begriff der Irreduzibilit&auml;t in der Theorie der linearen Differentialgleichungen</i>, Journal f&uuml;r die reine und angewandte Mathematik 76, 236--272 (1873).
• 3: L. Schlesinger, <i>Handbuch der Theorie der linearen Differentialgleichungen I-III</i>, Teubner, Leipzig, 1895--1898. These volumes have been reprinted by the Johnson Reprint Corporation in 1968.
• 4: E. Beke, <i>Die Irreduzibilit&auml;t der homogenen linearen Differentialgleichungen</i>, Mathematische Annalen 45, 278--294 (1894).
• 5: E. Landau, <i>&Uuml;ber irreduzible Differentialgleichungen</i>, Journal f&uuml;r die reine und angewandte Mathematik 124, 115--120(1902).
• 6: 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]
• 7: F. Schwarz, <i>Rational Solutions of Riccati Equations</i>, to appear.
• 8: M. Singer, <i>Liouvillian Solutions of n-th Order Homogeneous Linear Differential Equations</i>, American Journal of Mathematics 103, 661--682 (1981).
• 9: 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]
• 10: M. Singer, <i>Testing Reducibility of Linear Differential Operators: A Group Theoretic Perspective</i>, CATHODE Meeting, Schlo&szlig; Dagstuhl, September 1992.
• 11: M. Bronstein, <i>On Solutions of Linear Ordinary Differential Equations in their Coefficient Field.</i>
• 12: S. Abramov, <i>Rational Solutions of Linear Differential and Difference Equations with Polynomial Coefficients.</i>
• 13: L. K&ouml;nigsberger, <i>Allgemeine Untersuchungen aus der Theorie der Differentialgleichungen</i>, Teubner, Leipzig, 1882.
• 14: F. Schwarz, <i>LODES: Linear Ordinary Differential Equation Solver</i>, User Manual.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Algorithms, Theory