Algebra and Algorithms for Differential Systems
Évelyne Hubert
University of Waterloo, Ontario
^{1}
Algorithms Seminar
May 14, 1998
[summary by François Ollivier]
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
This talk investigates algorithmic issues related to the formal resolution of
algebraic differential systems, with a stress on the problem of
testing components inclusion. Index reduction and applications to
control theory are also considered.
News are also given of the diffalg2 maple package which improves
upon Boulier's work and will be part of a future Maple distribution.
1 Basic Algebraic Results
1.1 Differential Algebras
Details may be found in the classical book by Ritt [12],
which remains an illuminating reference. The two first chapters
provide a clear exposition of basic definitions and results. Some
details on the low power theorem may be found in chapter 3. The book
by Kolchin [9] is a reference book reserved to
those having a good familiarity with the subject. Chapter 2 of
Buium's book [3] is also a good introduction to
differential algebra. The remaining chapters may be quite hard without
a good previous knowledge of ``modern'' algebraic geometry, but
contain many interesting new results. The paper [6], and
thesis [8]
contain details on the components problem. Details on Boulier's
algorithm can also be found in [1, 2].
Differential algebra is a generalization of classical commutative
algebra. We complete the ring structure with the datum of a set of
mutually commuting derivations D={d_{1},
...,d_{n}}. We may then define differential fields, modules
and algebras in a straightforward way. A differential ideal of a
differential ring A is an ideal I such that d IÌ I,
for all dÎD. Let A be a differential ring, and I be
a differential ideal, then A/I has a natural structure of
differential ring. The smallest differential ideal containing a set
S is denoted by [S].
We define differential polynomials in the following way: if A is a
differential ring with derivation set D, Q the free
commutative monoid generated by D and X a set, the
differential polynomial algebra A{X} is the polynomial algebra
A[Q X] equipped with the only derivation set whose action
restricted to A and Q X is that of D.
Let A be a Ritt ring, i.e. a differential ring containing Q. Then
for every differential ideal IÌ A, the radical ideal (I)^{1/2}
is differential. A differential ring A is radically Noetherian if
for every set SÌ A there exists a finite set B such that
([S])^{1/2} = ([B])^{1/2}. In the sequel, we will denote the
perfect closure ([S])^{1/2} by {S}.
Theorem 1 [RittRaudenbush] If A is radically Noetherian, then
for all finite
set X, A{X} is radically Noetherian.
Corollary 1 Le I be a radical differential ideal, then I
is a finite intersection of prime ideals Ç_{i=1}^{r} P_{i}.
1.2 Differential Field Extensions
Let F be a differential field, and P be a prime
differential ideal of F{X}, then the quotient ring F{X}/ P is a differential domain, and we can consider its
fraction field K. So we can associate to any prime differential field
P a differential field extension K/ F.
It is clear from the theorem above that a system of equations
SÌ F{X} admits solutions in some field extension
of F iff {S}¹ 1. So we need an algorithm to test if
a system is consistent.
2 Algorithmic Tools
2.1 Boulier's Algorithm
Boulier's algorithm [2] is able to solve such problems
as eliminating differential variables, and testing consistency of a
differential system. It provides a description of the set of solutions
as a finite union of algebraic quasivarieties, i.e. Zariski open
subsets of differential algebraic varieties. Each of them is described
by a characteristic set A (see [12] for a precise
definition of this notion), according to a compatible ranking on the
set of derivatives, and an inequation h_{A}¹ 0. Let u_{P}
denote the greatest derivative of a polynomial P. The separant of
P is S_{P}:= ¶ P/¶ u_{P}. As h_{A} is a multiple
of the products of separants of polynomials in the characteristic set,
the ideal [A]:h_{A}^{¥} is radical. Unlike Ritt's algorithms,
Boulier's avoids factorizations for better efficiency. This is why it
cannot return prime components.
Boulier's algorithm first proceeds by constructing an autocoherent set
by repeated pseudo Euclidean reductions. An autocoherent set A being
found, one need to test that it is the characteristic set of a radical
differential ideal. According to Rosenfeld's Lemma, this may be
reduced to an algebraic problem. We only have to test that A is a
characteristic set of the algebraic ideal (A):h_{A}^{¥}. This
may be done by computing a Gröbner basis of the ideal (A, h_{A}w 
1), using an extra variable w and Rabinovich's trick.
2.2 Singular Solutions and Inclusion of Components
A difficult problem of differential algebra is to test whether two
irreducible components defined by their characteristic sets are
included one in the other. We are only able to test equality, and have
necessary conditions, sufficient conditions, but no necessary and
sufficient condition in the general case.
Consider a single polynomial equation: P(t, y, ..., y^{(r)}),
where P is prime. The
perfect ideal {P} is a finite intersection of prime ideals, P_{i}, associated to characteristic sets reduced to a
single polynomial A_{i}. The general component A_{1} is associated
to P. The other correspond to essential prime components
assuming that the P_{i} are not included one in the other.
Boulier's algorithm, like Ritt's algorithm, produces the characteristic
sets A_{i} of singular components, but also characteristic sets
B_{j} corresponding to the singular locus of the differential
algebraic variety corresponding to the general solution. (Notice that,
as we avoided factorizations, the A_{i} need not be
prime and can represent more than one prime component.) The B_{j}
and the A_{i} correspond to the solutions of the perfect ideal {P,
S_{P}}. We have {P}= {P, S_{P}}Ç {P}:S_{P}. The
solutions corresponding to non essential singular components are
Zariski adherent to the regular place of the general component.
We may remark, that according to [11], determining the
essential singular components is equivalent to finding a finite basis
of {P}:S_{P}, i.e. to have an effective version of the
RittRaudenbush theorem.
2.3 Some Effective Criteria of Inclusion
For a differential equation of order 1, the singular solutions are
envelopes of regular ones. E.g., for the equation (y')^{2}  4y,
the solutions in the general component are parabolas y(t)=
(t+c)^{2}, and the essential singular solution y=0 is the envelope
of these parabolas.
If we have a prime decomposition, we can obtain an algorithm for
finding the minimal essential components of {P} by using the low
power theorem of Ritt.
Theorem 2
The prime differential ideal {y} is an essential component of
{P}, iff the lower degree terms of P do not contain any strict
derivative of y.
From this, we deduce that {y} is not an essential component of
y'^{2}  4y^{3}. In such a case, the regular solutions are of the
form y(t)= 1/(t+c)^{2}. When t goes to infinity, then y goes to
0. So the solution y=0 is adherent to the the set of regular
solutions. See [12, Chap. 6] for analytical versions of
this adherence property.
The necessity proof relies of Levi's lemma which characterizes the
monomials belonging to the differential ideal [y^{p}]
[12, Chap. 2], or on Kolchin's domination lemma. The
sufficiency proof was obtained by Ritt, using a Puiseux series
expansion.
In the case where we want to test the inclusion
{P}:S_{P}Ì{Q}:S_{Q}, where Q¹ y, we need to find a
preparation polynomial, i.e. a polynomial M(z)=å_{g=0}^{l}
c_{g}m_{g}(z) such that c_{g} does not belong to
{Q}:S_{Q}, CP = M(Q) and C is not a zero divisor modulo
{Q}:S_{Q}. An algorithm is given to compute a preparation
polynomial.
We also have a low power theorem for regular differential polynomials
(see Hubert [7]). This theorem, together with Boulier's
algorithm allows to find a minimal regular
decomposition for {P} without performing factorizations.
Theorem 3
(Sufficiency)
Let P be a non zero differential polynomial of F{Y}, Q
a square free polynomial. Assume that the preparation polynomial of
P with respect to Q is M = cz^{p} + R, where RÎ [z]^{p+1},
p>0 and c is partially reduced with respect to Q. Then,
Q/gcd(Q,c) is the characteristic set of an essential singular
component of P.
(Necessity)
Under the same hypotheses, if the preparation polynomial is M= c_{0}z^{p}
+å_{g=1}^{l} c_{g}m_{g} + R, where
RÎ[z]^{p+1}, the c_{g} are partially reduced with respect
to Q, then Q/gcd(Q, c_{0}, ..., c_{l}) is a characteristic
set of a redundant component.
2.4 Implementations
The RosenfeldGröbner algorithm of Boulier, implemented in the Maple
package diffalg, has been improved with the new version diffalg2. Functions for computing preparation polynomials and finding
initial components were added. It is available on the Web with a
clear documentation, and an impressing set of examples.
3 Applications
3.1 Control Theory
Elimination in differential algebra allows to go from statespace to
inputoutput representation by eliminating the state variables. It
allows to test observability [4] and
identifiability [5, 10].
Consider a system of the form x_{i}' = P_{i}(x,u), y_{j}' =
Q_{j}(x). To test observability, one has to compute a characteristic
set for an ordering eliminating the variables x. The system is
observable iff for each variable x_{l}, the characteristic set
contains a polynomial whose x_{l} is the main derivative. Such a
polynomial gives an implicit expression of x_{l} as an algebraic
function of the outputs y and the inputs or commands u and
their derivatives. This makes such an expression of little
applicability, due to the noise.
3.2 Implicit Systems
If we consider an implicit system P_{i}(x', x)=0 where det(¶
P_{i}/¶ x_{j}'), it is not possible to compute a power series or
a numerical solution in a direct way. The system is not formally
integrable. In fact, solutions, if any, do not exist for all initial
conditions, and one may need first to determine the variety of
compatible initial conditions. For this, one will need to differentiate
the equation a number of time which is known as the index of the
system. Computing characteristic sets, using the Rosenfeld Gröbner
algorithm is a way of doing it.
References
 [1]

Boulier (François), Lazard (Daniel), Ollivier (François), and Petitot
(Michel). 
Computing representations for radicals of finitely generated
differential ideals. 
1997. Submitted to JSC.
 [2]

Boulier (Frangois), Lazard (Daniel), Ollivier (Frangois), and Petitot
(Michel). 
Representation for the radical of a finitely generated differential
ideal. In Levelt (A. H. M.) (editor), ISSAC'95. pp. 158166. 
Montréal, Québec, 1995.
 [3]

Buium (Alexandru). 
Differential Algebra and Diophantine Geometry. 
Hermann, Paris, 1994, Actualités
mathématiques.
 [4]

Fliess (Michel) and Diop (Sette). 
On nonlinear observability. In Proceedings of the First European
Control Conference. vol. 1, pp. 152157. 
Hermès, July 1991.
 [5]

Glad (S. T.) and Ljung (L.). 
Parametrization of nonlinear model structures as linear regressions.
In Proceedings of IFAC World Congress. 
August 1990.
 [6]

Hubert (Évelyne). 
The general solution of an ordinary differential equation. In
Lakshman (Y. N.) (editor), ISSAC'96, pp. 196203. 
Zürich, Switzerland, July 1996.
 [7]

Hubert (Évelyne). 
Essential components of an algebraic differential equation. 
1997. Submitted.
 [8]

Hubert (Évelyne). 
Étude algébrique et algorithmique des singularités
des équations différentielles implicites (Algebra and Algorithms for
Implicit Differential Equations). 
PhD thesis, Institut national polytechnique de Grenoble, April
1997.
 [9]

Kolchin (E. R.). 
Differential Algebra and Algebraic Groups. 
Academic Press, New York, 1973.
 [10]

Ollivier (François). 
Le problème de l'identifiabilité structurelle globale :
étude théorique, méthodes effectives et bornes de
complexité. 
PhD thesis, École polytechnique, Palaiseau, France, June
1990. URL: http://medicis.polytechnique.fr/gage/ollivier.html.
 [11]

PéladanGerma (Ariane). 
Tests effectifs de nullité dans les extensions d'anneau
différentiels. 
PhD thesis, École polytechnique, January 1997.
 [12]

Ritt (Joseph Fels). 
Differential Algebra. 
American Mathematical Society, New York, N. Y., 1950,
American Mathematical Society Colloquium Publications, vol. XXXIII,
viii+184p.
 1
 http://daisy.uwaterloo.ca:80/~ehubert/Diffalg/
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.