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
ak(x)=(x-x)
bk
hk(x), hk(x)¹0, k=0,...,n,
a rational solution y(x), which necessarily belongs
to K^(x), may be written
y(x)=(x-x)rz(x)
where x is neither a zero nor a pole of z(x). The term
ak(x)y(k)(x) of (1) behaves like
r(r-1)···(r-k+1)
a
(bk)
k
bk!
(x-x)
r+bk-k
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 equationEx(r);
this equation is the coefficient of the lowest power of x-x in
n
å
k=0
r(r-1)···(r-k+1)
a
(bk)
k
bk!
(x-x)
bk-k
.
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.
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.