Algebra and Algorithms for Differential Systems

Algebra and Algorithms for Differential Systems

Évelyne Hubert

University of Waterloo, Ontario¹

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₁, ...,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 [Ritt-Raudenbush] 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_Aw - 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₁ 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 Ritt-Raudenbush 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')² - 4y, the solutions in the general component are parabolas y(t)= (t+c)², 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'² - 4y³. In such a case, the regular solutions are of the form y(t)= 1/(t+c)². 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_gm_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₀z^p +å_g=1^l c_gm_g + R, where RÎ[z]^p+1, the c_g are partially reduced with respect to Q, then Q/gcd(Q, c₀, ..., c_l) is a characteristic set of a redundant component.

2.4 Implementations

The Rosenfeld-Grö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 state-space to input-output 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. 158--166. -- 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. 152--157. -- Hermès, July 1991.
[5]: Glad (S. T.) and Ljung (L.). -- Parametrization of non-linear 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. 196--203. -- 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éladan-Germa (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^AT_EX by H^EV^EA.