Minimal Decomposition and Computation of Differential Bases for
an Algebraic Differential Equation
Évelyne Hubert
LMC, Grenoble
Algorithms Seminar
September 21, 1996
[summary by Bruno Salvy]
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).
Abstract
Singular and general solutions of algebraic differential equations
can be expressed in a differential algebra setting regardless of the
existence of closedform. Theoretical and algorithmic tools in this
area are presented.
1 Types of solutions
Consider the following differential equation:
y'
^{3}4
xyy'+8
y^{2}=0.
(1)
This equation admits three solutions of different types:
y(x)=a(xa)^{2}, y(x)=0, y(x)= 

x^{3}.
(2) 
The first one is the general solution and the two other ones
are singular solutions. The solution y(x)=0 is actually a
special case of the general solution and is called a particular singular solution; the third one is an essential singular solution. As showed by Figure 1,
both singular solutions appear as envelopes of the general
solution. In general, this is true of essential singular
solutions of first order equations.
Figure 1: Solutions of (
1)
In the general case of an equation
P(x,y,y',...,y^{(n)})=0,
where P is a polynomial, the singular solutions are the
simultaneous solutions of P
and its separant ¶ P/¶ y^{(n)}. Through
differential algebra, a meaning can
also be given to the ``general'' solution
even when no closedform exists. It is also possible to distinguish
algebraically between a particular singular solution and an essential
one. The aim of É. Hubert's work is to provide algorithms dealing
with general and singular solutions in this framework.
To an ordinary differential equation like (1) is
associated a differential polynomial
p=y_{1}^{3}4xy_{0}y_{1}+8y_{0}^{2}ÎQ(x){y}.
More generally, the differential ring A=A{y} is a ring of
polynomials in the
variables y_{0},y_{1},y_{2},... endowed with an operator d which
is a derivation on the commutative integral domain A and which is
such that d
y_{i}=y_{i+1}. A differential ideal is an ideal stable
under d. For instance the differential ideal generated by a
differential polynomial p is the polynomial ideal generated by p
and its derivatives:
[p]=(p,d p,d^{2}p,...).
Of particular interest is the radical of this ideal:
{p}=([p])^{1/2}={aÎA $ kÎN, a^{k}Î[p]}.
This is the set of differential polynomials vanishing on all the solutions
of p. A differential ideal I is prime when abÎ
IÞ aÎ I or bÎ I.
We now restrict to A=Q(x) for simplicity, but the results can be
stated in much more generality, see [4, 5]. An
important property is that a radical differential ideal R can be
decomposed into a finite intersection of prime differential ideals:
When none of the P_{k} is included in another one, this decomposition
is called minimal and is unique. These P_{k}'s are then called
essential components of R. In the same way as {p}
corresponds to the solutions of p, each of the essential components
of {p} corresponds to one type of solutions of p.
In the same
example as before, a decomposition is
{p}={p,y_{2}^{2}2xy_{2}+2y_{1},y_{3}}Ç{y_{0}}Ç{27y_{0}4x^{3}},
each term corresponding to one of (2). This
decomposition is not minimal since the second ideal obviously contains
the first one and therefore corresponds to a particular singular solution.
The minimal decomposition is obtained by removing this second
term. Testing the inclusion of the general component (the first one here)
into one of the other ones is related to Ritt's problem; its
algorithmic resolution via the computation of a
differential basis of each component is one of the aims of [3].
While the singular solutions obviously correspond to components of the
ideal {p,s}, where s is the separant of p, the general
solution corresponds to the quotient of {p} by s, where
the quotient of a radical differential ideal R by an
element sÎA is defined as
R:s={aÎA saÎ R},
which is itself a radical differential ideal. Two properties are of
interest: for
any nonempty subset s of A, one
has {s}={s}:sÇ{s,s}; when p is irreducible
as a polynomial in y_{0},y_{1},... and s is its separant, the
ideal {p}:s is prime. Thus G_{p}={p}:s is an essential
component of {p} which is called the general component of p.
2 Algorithms for minimal decompositions
We now turn to the actual computation of the minimal decomposition
{p}= G_{p}Ç R_{1}Ç...Ç R_{k}.
Ritt showed that each essential component R_{i} is the
general component of some differential
polynomial a_{i}. The computation of a minimal decomposition then
requires finding these a_{i}'s and insuring that the decomposition is
minimal.
Ritt's low power theorem states that when an irreducible
differential
polynomial p of a differential ring A{y_{1},...,y_{n}} is
contained in one of the
ideals {y_{i}}, then {y_{i}} is an essential component of {p}
if and only if the lowest degree terms of p do not contain a
derivative of y_{i}. This theorem can be used to give a criterion for
a G_{a} to be an essential component of {p} after a preparation process which rewrites p as a differential polynomial
in a:
where s_{a} is the separant of a, a_{i}=d^{i} a,
c_{a}_{0}_{,...,a}_{e}Ï G_{a} and e is the
difference between the order n of p and the order m of a.
This reduction process is performed in three stages: for i from 1
to e, a_{i}=d a_{i1} can be rewritten a_{i}=s_{a}y_{m+i}+t_{i} for
some t_{i}. Then y_{n} is replaced by (a_{e}t_{e})/s_{a} in p. After
normalization this yields
where the coefficients do not involve derivatives higher
than y_{n1}. The process is then repeated with the y_{ni} in
succession. This rewrites all the y_{m+i} for i>0. Then in each
monomial c_{a}a_{1}^{a}_{1}··· a_{e}^{a}_{e},
the coefficient c_{a} is
rewritten c^{~}_{a}a_{0}^{a}_{0},
where a_{0} is the largest integer k such that a^{k} divides
c_{a}.
In our previous example, the reduction of p in terms of y_{0} is
tautologous; the lowest degree terms of p is 4xy_{0}y_{1}+8y_{0}^{2} and
thus {y_{0}} is not an essential component. The reduction of p in
terms of a=27y_{0}4x^{3} is more interesting. The separant s_{a}=27
is constant and the first step of the reduction process
yields a_{1}=27y_{1}12x^{2}. Then p is rewritten successively
p 
=y_{1}^{3}4xy_{0}y_{1}+8y_{0}^{2}, 
19683p 
=a_{1}^{3}+36x^{2}a_{1}^{2}108x(27y_{0}4x^{3})a_{1}+216(27y_{0}2x^{3})(27y_{0}4x^{3}), 
19683p 
=a_{1}^{3}+36x^{3}a_{1}^{2}108xa_{0}a_{1}+216(27y_{0}2x^{3})a_{0}. 
The lowest degree term is 216(27y_{0}2x^{3})a_{0} which does not
involve a_{1} and thus {27y_{0}4x^{3}} is an essential
component. (There also exists a simpler algorithm in this case
since p is of order 1 [2]).
The computation of the a_{i}'s relies on the RosenfeldGröbner
algorithm [1] which has been implemented in Maple
by F. Boulier. Given a system S of differential
polynomials and a ranking, this algorithm computes a decomposition of
the radical ideal {S} as a finite intersection of radical
differential ideals:
{S}= I_{1}Ç...Ç I_{s},
each I_{i} being described by a system of polynomial
equations and inequations and a characteristic set. This
decomposition makes it possible to test membership in
the I_{i}'s and therefore in {S} by simple
reductions. Note that the I_{i}'s are not necessarily
prime.
A lemma of Lazard's combined with Ritt's result mentioned
above shows that the I_{i}'s corresponding to essential
components of {p,s} must have a characteristic set reduced to one
differential polynomial. This makes it possible to filter out some of
the radical ideals. Then prime differential ideals can be obtained by
factorization. This leads to the following algorithm.
Input: An irreducible differential polynomial p.
Output: a_{1},...,a_{r} such
that G_{p}, G_{a}_{1},..., G_{a}_{r} are the
essential components of {p}.
G:=RosenfeldGröbner([p,s]);
A:=[];
for each R in G with cardinality 1 do

for each factor b of R[1] do

if lowpowers(preparation(p,b))=cb_{0}^{r} then
A:=AÈ[b];

Return A.
In our example, the output of RosenfeldGröbner is
{y_{0}}, {27y_{0}4x^{3}},
from where the computations above have been performed.
It is possible to avoid the factorization and perform only gcd
computations.
In some cases, this algorithm can also be extended to compute a differential
basis of G_{p}. This is helpful to compute power series
solutions when the initial conditions lie on a singular solution.
We refer to [3] for details.
References
 [1]

Boulier (F.), Lazard (D.), Ollivier (F.), and Petitot (M.). 
Representation for the radical of a finitely generated differential
ideal. In Levelt (A. H. M.) (editor), Symbolic and Algebraic
Computation. pp. 158166. 
New York, 1995. Proceedings of ISSAC'95, July 1995,
Montreal, Canada.
 [2]

Hubert (Évelyne). 
The general solution of an ordinary differential equation. In
Lakshman (Y. N.) (editor), Symbolic and Algebraic Computation.
pp. 189195. 
New York, 1996. Proceedings ISSAC'96, Zürich, July
1996.
 [3]

Hubert (Évelyne). 
Étude algébrique et algorithmique des singularités
des équations différentielles implicites. 
PhD thesis, Institut National Polytechnique de Grenoble, April
1997.
 [4]

Kolchin (E. R.). 
Differential algebra and algebraic groups. 
Academic Press, New York, 1973, Pure and Applied
Mathematics, vol. 54, xviii+446p.
 [5]

Ritt (Joseph Fels). 
Differential Algebra. 
American Mathematical Society, New York, N. Y., 1950,
American Mathematical Society Colloquium Publications, vol. XXXIII,
viii+184p.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.