An Efficient Algorithm to Compute
the Rational Solutions of a Linear Differential System

Moulay Barkatou

LMC-IMAG Université de Grenoble I

Algorithms Seminar

January 27, 1997

[summary by Philippe Dumas]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

The talk is in two parts: first a presentation of Abramov's algorithm for linear differential equations, next a generalisation to differential systems.

The aim of Abramov's algorithm [3] is to find all rational solutions of a linear differential equation with polynomial coefficients, that is an equation of the form
an(x)y(n)(x)+...+a1(x)y'(x)+a0(x)y(x)=b(x),     (1)
where an(x),...,a0(x), b(x) are polynomials. The first step of the algorithm is to bound the denominator g(x) of a possible solution f(x)/g(x). By a bound, we mean a polynomial q(x) such that g(x) divides q(x). The coefficients of the polynomials ak(x) lie in a number field K. The key argument uses the splitting field K^ of the polynomial an(x). If x is a root of an(x) and the coefficients read
hk(x),     hk(x)¹0,   k=0,...,n,
a rational solution y(x), which necessarily belongs to K^(x), may be written
where x is neither a zero nor a pole of z(x). The term ak(x)y(k)(x) of (1) behaves like
near x. But the right-hand side of (1) is a polynomial, hence the exponent r is larger or equal to the minimal integer root -r of the indicial equation Ex(r); this equation is the coefficient of the lowest power of x-x in
This crude description does not give an efficient way to obtain a bound of the denominator g(x). Indeed it is possible to avoid any use of K^(x) by greatest common divisor techniques. Essentially the previous argumentation is applied to each irreducible factor f(x) of an(x) in place of each x-x to give an indicial equation Ef(r)=0. As a result, a bound q(x) for the denominator is obtained.

Next p(x)/q(x) substitutes for y(x) into (1) and the polynomial p(x) is to be determined. This is the second step of the algorithm. The degree of p(x) is the order of ¥ as a pole of a solution, and the technique of the first step provides a bound N for the degree of a polynomial solution. At this point it is possible to proceed by brute force collection of like powers of x, but the bound N is not accurate. It is more efficient to find the coefficient pN of xN in p(x) and to write p(x)=pNxN+p*(x) with p*(x) a polynomial of degree at most N-1. In this manner, the coefficients of p(x) are obtained in turn. If there is no rational solution the process stops at some stage.

The classical approach for the search of rational solutions of linear differential systems consists in reducing them to the scalar case. This idea goes back to Birkhoff [5, 7]. The reduction uses the concept of cyclic vectors. Its major drawback is the growth of coefficients.

Barkatou [4] proposes a direct approach to the linear differential systems, which uses the same ideas as Abramov's algorithm. The difference is the use of matrices instead of scalars, as exemplified in [6] or [8]. The differential system under consideration reads
d(x)Y'(x)-A(x)Y(x)=B(x),     (2)
where A(x) is a square matrix and B(x) is a vector, both with polynomial components. The coefficient d(x) is a polynomial; for each irreducible factor f(x) of d(x) there is an indicial equation Ef(r). Contrary to the scalar case, the indicial equation may reduce to 0=0, but a convenient linear change of variables eliminates this problem. The indicial equation gives a bound for each irreducible factor of d(x), and a bound for a common denominator of the components of Y(x). It remains to determine a polynomial solution of linear differential system, as in the scalar case.


Abramov (S. A.). -- Rational solutions of linear differential and difference equations with polynomial coefficients. USSR Computational Mathematics and Mathematical Physics, vol. 29, n°11, 1989, pp. 1611--1620. -- Translation of the Zhurnal vychislitel'noi matematiki i matematichesckoi fiziki.

Abramov (S. A.). -- Rational solutions of linear difference and q-difference equations with polynomial coefficients. In Levelt (A.) (editor), Symbolic and algebraic computation. pp. 285--289. -- New York, 1995. Proceedings of ISSAC'95, Montreal.

Abramov (S. A.) and Kvashenko (K. Yu.). -- Fast algorithms to search for the rational solutions of linear differential equations with polynomial coefficients. In Watt (Stephen M.) (editor), Symbolic and algebraic computation. pp. 267--270. -- New York, 1991. Proceedings of ISSAC'91, Bonn.

Barkatou (Moulay). -- An efficient algorithm to compute the rational solutions of systems of linear differential equations. -- Preprint, 1997.

Birkhoff (G. D.). -- Formal theory of irregular linear difference equations. Acta Mathematica, vol. 54, 1930, pp. 205--246.

Coddington (E. A.) and Levinson (M.). -- Theory of Ordinary Differential Equations. -- McGraw-Hill, 1955. Twelfth reprint 1991 of the Tata McGraw-Hill edition 1972.

Hilali (Abdelaziz). -- Solutions formelles de systèmes différentiels linéaires au voisinage d'un point singulier. -- Doctorat d'État, Université scientifique, technologique et médicale de Grenoble, June 1987.

Wasow (Wolfgang). -- Asymptotic expansions for ordinary differential equations. -- Dover Publications Inc., New York, 1987, x+374p. Reprint of the John Wiley 1976 edition.

This document was translated from LATEX by HEVEA.