An Efficient Algorithm to Compute
the Rational Solutions of a Linear Differential System
LMC-IMAG Université de Grenoble I
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
The aim of Abramov's algorithm  is to find
all rational solutions of a linear differential equation with
polynomial coefficients, that is an equation of the form
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
a rational solution y(x), which necessarily belongs
to K^(x), may be written
||hk(x), hk(x)¹0, k=0,...,n,
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  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  or . The
differential system under consideration reads
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
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. --
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