Effective Algebraic Analysis in Linear Control Theory

University of Leeds (United Kingdom) & Projet Café, Inria Sophia-Antipolis (France)

Algorithms Seminar

December 4, 2000

[summary by Frédéric Chyzak]

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
In the 1960's, Malgrange made use of D-module theory for studying linear systems of PDEs [2]. Several aspects of this approach, now called algebraic analysis, have then been made effective in the 1990's, owing to the extension of the theory of Gröbner bases to rings of differential operators. Correspondingly, algorithms have also been implemented in several systems. Recently, the introduction of algebraic analysis to control theory has allowed to classify linear multidimensional control systems according to algebraic properties of associated D-modules, to redefine their structural properties in a more intrinsic fashion, and to develop effective tests for deciding these structural properties [3, 6, 7, 8, 9, 10, 12, 14].

1  From Linear Multidimensional Control Systems to Algebraic Analysis

A control system relates the state x of a physical process with an external command u and some output y. Each of u, x, and y is a vector of functions of the time t, and the system describes their evolution with t. Several classes of such systems can be represented by matrices with coefficients in a ring of operators. Sample classes are the following:
1. Kalman systems are first-order linear (ordinary) differential systems
 . x
=Ax+Bu,     y=Cx+Du,
where A, B, C, and D are matrices with real entries [5]. For example, RLC circuits can be described by Kalman systems.
2. Polynomial systems are higher-order differential systems expressed without the help of any state variable, in the form
P(d/dt)y(t)+Q(d/dt)u(t)=0.     (1)
Here P and Q are matrices with coefficients that are scalar linear differential operators with real coefficients [5]. For example, a harmonic oscillator commanded by a force is described by a second-order polynomial system. By Laplace transform, an equivalent formulation of (1) is
P(s)
 ^ y
(s)+Q(s)
 ^ u
(s)=0;
the matrices P and Q are now matrices of polynomials in s with real coefficients [5].
3. Differential-delay systems with constant delays are a generalization common to Kalman systems and polynomial systems by introducing the constant-delay operators di defined by (dif)(t)=f(t-ti) for some real ti. The generalized forms are
 . x
(t)=
 r å i=0
Aix(t-ti)+Biu(t-ti),     y(t)=
 r å i=0
Cix(t-ti)+Diu(t-ti),
and
P(d/dt,d1,...,dr)y+Q(d/dt,d1,...,dr)u=0,
respectively. A typical occurrence of delay is when transmitting a signal u through a channel.
4. Multivariate linear differential systems with real coefficients appear frequently to describe physical phenomena, like electromagnetism, (linear) elasticity, hydrodynamism, and so on [7, 8, 12].
In each case, the column vector x=(y,x,u)T satisfies Rx=0 for a (rectangular) matrix R with coefficients in some ring A. Thus, we henceforth consider a linear control system as defined by a matrix R with coefficients in an entire ring A. To give simple examples, the matrix forms corresponding to Kalman and polynomial systems respectively are
R= æ
è
 0 A-d/dt Id B Id C D
ö
ø
and     R= (
 P Q
) .
In these differential cases, the ring A is R[d/dt] or a multivariate generalization, but more general rings of coefficients are also considered in place of R in applications, like the ring R(t) of rational function, or the ring C¥(I) of infinitely differentiable functions over some real interval I. In the equivalent formulation by Laplace transform or in the mixed differential-delay situation with constant coefficients, the ring is isomorphic to the polynomial ring R[s] or a multivariate analogue. Here again, more general rings of functions often appear in applications, like: R[s,exp(-s)], for situations related to the wave equation; or the ring H¥(C+) of complex-analytic functions bounded in the right half complex plane C+ (Hardy space) and its subring RH¥(C+) of real rational functions with no pole on the right half complex plane, for the study of the stability of some distributed systems [11].

Several structural properties of systems are all-important in control theory. An observable of a control system is any scalar function of its command u, state x, and output y and of their derivatives up to a certain order. An observable is called autonomous if it satisfies a non-trivial PDE. A control system is called controllable if no observable is autonomous. The study of structural properties of a system turns out to lead to linear algebra: controllability and observability are related to various notions of primeness of the linear maps
z|® Rz    and     z|® zR;
in the polynomial systems case, stability is related to poles and zeroes of the system, that are invariant factors of the matrix R; similarly with the existence of generalized Bézout identities and flatness of a control system; etc.

By associating an A-module M to the matrix R, another interpretation of the structural properties is in terms of module-theoretic and homological properties of M (torsion, torsion-free, reflexive, and projective modules; extension and torsion functors). In fact, a full classification of modules by homological algebra methods translates into a classification of linear control systems.

2  Duality Between Differential Operators and D-Modules

Let us turn to the formal theory of PDEs [13]. Starting with a naive viewpoint on differential operators (so as to avoid the formalism of jet bundles), we introduce formally exact sequences of differential operators. For each k, let Fk denote the algebra of functions in k variables, and consider a differentiel operator D from Fm to Fl (of finite order). Given hÎ Fn, the necessary conditions for the existence of xÎ Fm such that Dx=h are called compatibility conditions of D; they take the form D1h=0 for some differential operator D1. Writing D0=D, we have D1°D0=0. When D1 encapsulates all compatibility conditions, the sequence
Fm
 D0 ®
Fl0
 D1 ®
Fl1
of differential operators is called formally exact (at Fl0). Formally exact sequences can always be extended (to the right) into longer sequences, so that denoting the solution set of D=D0 in Fm by Q, we obtain a formally exact sequence
0®Q® Fm
 D0 ®
Fl0
 D1 ®
Fl1
 D2 ®
Fl2®···
(at Q and each Flk) where the first two maps denote inclusions. Under technical conditions (regularity and involutivity), the formal theory of PDEs proves the existence of a finite formally exact sequence for D, in the sense that Fln=0 from some n on, by exhibiting a canonical, formally exact sequence
0®Q=kerD0® Fm
 D0 ®
Fl0
 D1 ®
Fl1
 D2 ®
Fl2®···
 Dr ®
Flr®0     (2)
called the Janet sequence of D, in which each (non-zero) Di is of order 1 (and involutive) for i³1, and r is the number of derivatives.

A dual, more algebraic counterpart to this differential viewpoint is in terms of exact sequences of D-modules. To this end, we now view each Di as defined by an li× li-1 matrix Ri of multivariate linear differential operators in
A=R(x1...,xr)[1,...,r].
(We set l-1=m.) In terms of matrices,
Di=Ri·=(x|® Rix),
so that Ri+1Ri·=0. We then consider the maps · Ri from Ali to Ali-1, whose elements are viewed as row vectors. To start with, the map · R0 defines an algebraic representation of a generic solution x the PDE system D0x=0 in the following way. Let (e1,...,em) be the canonical basis of Am and consider the maps
0¬ M=Am/Al0R0
 p ¬
Am
 · R0 ¬
Al0,     (3)
where p denotes the canonical projection p(v)=v+Al0R0. The cokernel
M=coker(· R0)=Am/Al0R0
of · R0 contains the announced generic solution: setting
xi=p(ei)=ei+Al0R0,
we get D0x=x R0=0. Other members of M correspond to linear combinations of the xi and their derivatives, i.e., to the observables defined above. We now proceed to follow up with the next Di's. A sequence
L
 u ®
L'
 v ®
L''
of linear maps (between modules) is said to be exact (at L') if im u=kerv. (Thus (3) is exact at M and Al0.) It can be shown that any Janet sequence (2) gives rise to the exact sequence
0¬ M
 p ¬
Am
 · R0 ¬
Al0
 · R1 ¬
Al1
 · R2 ¬
Al2¬···
 · Rr ¬
Alr¬0     (4)
(at M and each Alk). Here, · Ri+1Ri=0 by exactness. Since A has no zero divisor, this means that Ri+1Ri=0. The sequence (4) of (left) D-modules is called a free resolution of M: it encapsulates the obstruction of M to be free (as the module kerp=im(· R0)), then the obstruction of kerp to be free (as the module ker(· R0)=im(· R1)), etc. (A module is called free when it is isomorphic to some Ar, whence the name ``free resolution.'')

3  Parametrization and Controllability

A problem dual to the search of compatibility conditions is, for a given differential equation Dx=0, to determine whether the solutions can be parametrized by certain arbitrary functions which, in physical systems, play the role of potentials. In other words, the problem is to determine whether there exists another operator
D-1:Fl-1® Fl0
whose compatibility conditions are described by D=D0, i.e., to look for a formally exact sequence
Fl-1
 D-1 ®
Fl0
 D0 ®
Fl1.
In this situation, for any xÎ Fl0 the existence of pÎ Fl-1 satisfying D-1p=x is equivalent to the fact that x solves the differential equation D0x=0, and so D-1 ``parametrizes''---in the usual sense---all its solutions.

The existence of a parametrization has a nice application to optimal command: assume one needs to minimize a cost function provided by the integral ò0tF(tdt of an observable F of some system D0. The optimization problem is then to minimize over all tuples x=(y,x,u)T of functions constrained by D0x=0. On the other hand, once the solutions x are given by a parametrization x=D-1p, the optimization problem reduces to the non-constrained problem of minimizing the integral ò0tG(tdt of a new observable G of D-1 over unconstrained p [12].

To study the control-theoretic properties of the differential operator D, starting with the existence of a parametrization, we in fact study the module-theoretic properties of M, which in turn are derived from the study of the right D-module defined by
Al-1
 R0· ®
Al0® N=coker(R0·)=Al0/R0Al-1®0     (5)
(recall that l-1=m and compare with (3)). The key ingredient to be used comes from linear algebra: dualization, which maps a left A-module L to the right module homA(L,A) of A-linear applications from L to A. Correspondingly, any linear map L
 u ®
L' induces a map from the dual of L' to the dual of L: to lÎhomA(L',A), one associates l° uÎhomA(L,A). This takes a simple form when the modules are free and of finite rank (i.e., L=Am and L'=Al, viewed as left modules of row vectors). Indeed, the linear map u is just the application of an m× l matrix U: u=· U. Elements µÎhomA(Ak,A) are defined by their values on the canonical basis (ei) of Ak by
 µ=· ( µ(e1),...,µ(ek) ) T,
so that the dual of Ak is isomorphic to Ak (now viewed as a right module of column vectors). In this setting, the dual of a map Am
 · U ®
Al is Am
 U· ¬
Al. The same ideas apply mutatis mutandis for the dual of right modules.

To search for a parametrization, one thus extends the exact sequence (5) into an exact sequence
Al-2
 R-1· ®
Al-1
 R0· ®
Al0 ® N®0.
An algorithm for this purpose will be given in Section 5. By dualization (i.e., application of the homA(·,A) functor), it becomes a sequence
Al-2
 · R-1 ¬
Al-1
 · R0 ¬
Al0 ¬homA(N,A)¬0
of left D-modules that is usually no longer exact. In particular, we may well have ker(· R-1) strictly larger than im(· R0). Upon forgetting the map · R0 and prolonging · R-1 into
Al-2
 · R-1 ¬
Al-1
 · R'0 ¬
Al'0,
we obtain an ``exact'' representation of ker(· R-1) as im(· R'0). It can be proved that the quotient
im(· R'0)/im(· R0)Í M
is the torsion module t(M) of M, i.e., the set of all its members m for which there exists a non-zero scalar aÎA such that am=0. Thus we have obtained that a (linear) control system system is controllable if and only if its associated module M of observables is torsion-free, which can be tested algorithmically. Moreover, a basis for the module t(M) of autonomous elements is obtained from the rows of R'0 (that are elements of im(· R'0)), viewed modulo im(· R0).

4  More Structural Properties of Control Systems as Extension Modules

Other structural properties of D will be described in terms of the extension modules of N, a central tool in homological algebra. Consider a free resolution
···
 R-n· ®
Al-n
 R-n+1· ®
···
 R-2· ®
Al-2
 R-1· ®
Al-1
 R0· ®
Al0 ® N®0     (6)
(as obtained, for example, with the algorithms of Section 5). This is an exact sequence of right D-modules. By dualization it becomes a sequence
···
 · R-n ¬
Al-n
 · R-n+1 ¬
···
 · R-2 ¬
Al-2
 · R-1 ¬
Al-1
 · R0 ¬
Al0 ¬homA(N,A)¬0     (7)
of left D-modules that, again, is usually no longer exact. By dropping homA(N,A) from (7), we obtain another non-exact sequence, but of free modules only,
···
 · R-n ¬
Al-n
 · R-n+1 ¬
···
 · R-2 ¬
Al-2
 · R-1 ¬
Al-1
 · R0 ¬
Al0 ¬0.
Its defects of exactness are encapsulated by its cohomology sequence, that is to say, by the quotients
ker(· R-i)/im(· R-i+1).
An all-important fact is that this family depends on N only, and not of the choice of a free resolution (6). This motivates the notation
extAi(N,A)=ker(· R-i)/im(· R-i+1)
for extension modules (with in particular extA0(N,A)=ker(· R0)=homA(N,A)).

The nullity or non-nullity of the exti's provides with the classification of modules in Theorem 1 below; in turn this classification provides with the classification of control systems in Theorem 3 below. Here are two more module-theoretic notions missing to state Theorem 1. A module L is projective whenever there exists a module L' such that LÅ L' is free; it is reflexive whenever it is isomorphic to the dual of its dual through the linear map
 e:M®homA ( homA(M,A),A )
defined by
e(m)(f)=f(m).
Then, a free module is always projective, a projective module always reflexive, and a reflexive module always torsion-free. (For modules over a principal ideal, these notions coincide; for modules over a multivariate polynomial ring with coefficients over a field, free and projective are equivalent, a theorem by Quillen and Suslin.)

The following theorems [1, 4] make the link between properties of a module and the nullity of the extension modules of its transposed module.
Theorem 1  [Palamodov, Kashiwara]   For the modules M and N defined by (3) and (5), we have:
1. M is torsion-free if and only if extA1(N,A)=0;
2. M is reflexive if and only if extA1(N,A)=extA2(N,A)=0;
3. M is projective if and only if extA1(N,A)=...=extAr(N,A)=0.
Theorem 2  [Palamodov, Kashiwara]   Let M and N be the two modules defined by (3) and (5). Then there exists an exact sequence
0® M®Ap1®Ap2 ®...®Apr
if and only if extAi(N,A)=0 for i=1,...,r.

We finally obtain the following classification of linear control systems, which admits some refinements in the case of differential operators with constant coefficients, i.e., matrices with entries in R[1,...,r]ÌA [7, 8, 12].
Theorem 3   For a control system defined by the differential operator D=R· where R is an l× m matrix with l£ m and entries in
A=R(x1...,xr)[1,...,r],
introduce the two left D-modules M=coker(· R) and N=coker(R·) of the maps between the free modules Am and Al. Then:
1. if M has torsion, the control system has autonomous elements, and in the event R has constant coefficients and full row module, it has no primality property;
2. M is torsion-free if and only if extA1(N,A)=0. In this case, the control system is controllable, and in the event R has constant coefficients and full row module, it is prime in the sense of minors, i.e., there is no common factor between the minors of R of order l;
3. M is reflexive if and only if extA1(N,A)=extA2(N,A)=0;
4. in the event R has constant coefficients and full row module, and if
extA1(N,A)=...=extAr-1(N,A)=0     while     extAr(N,A)¹0,
the control system is weakly prime in the sense of zeroes, i.e., all minors of order l simultaneously vanish at finitely many points only;
5. M is projective if and only if
extA1(N,A)=...=extAr(N,A)=0.
In this case the control system has an inverse generalized Bézout identity, and in the event R has constant coefficients and full row module, it is prime in the sense of zeroes, i.e., all minors of order l simultaneously vanish at no point;
6. if M is free, the control system is flat and has direct and inverse generalized Bézout identities.
Further intermediate situations, extA1(N,A)=...=extAk-1(N,A)=0 and extAk(N,A)¹0, correspond to further intermediate primeness conditions (described in terms of the dimension of the algebraic variety defined by the l× l minors of R).

5  Gröbner Basis Calculations for Compatibility Conditions and Parametrizations

The whole machinery of the previous sections crucially bases on prolongations of exact sequences. A point that is important in view of computations is that these can be obtained by Gröbner basis calculations for free modules over A.

The prolongation of a map Am
 · R ¬
Al into an exact sequence Am
 · R ¬
Al
 · S ¬
Ak is done in the following fashion. Let (e1,...,em) and (f1,...,fl) be the canonical bases of Am and Al, respectively, and denote the ith row of R=(ri,j) by hi. Thus hi=åj=1mri,jej. Prolonging the map amounts to finding non-trivial relations åi=1lsihi=0. Now introduce the submodule Z of Am+l generated by the formal linear combinations fi-hi. We contend that computing a Gröbner basis for this module and for a term order that eliminates the ei results in linear combinations åi=1lsifiÎ Z, each of which corresponds to a relation between the hi. Additionally, any relation can be obtained as a linear combination of the relations thus obtained.

In effect, consider an element z=åi=1lsifiÎ Z; thus åi=1lsihi is in Z and is a combination åi=1lli(fi-hi), which is only possible, in view of the coefficients of the fi, if the li are zero, thus if åi=1lsihi=0; the converse property is also true. Since the Gröbner basis calculation precisely computes a finite generating set, say of k elements, for all the z's free of the ei, it suffices to consider each of those k elements as a row, and to glue them in column to obtain a new matrix S=(Si,j) such that the sequence Am
 · R ¬
Al
 · S ¬
Ak is exact.

Now, existing packages often contain facilities to compute Gröbner bases for left modules only; some of our computations require to deal with right modules. A last ingredient, adjunction, enables one to turn any left module into a right module, and vice versa, in a way that preserves the exactness of sequences. Indeed, the adjoint map P|®P~ defined by associativity from the rules xi~=xi, i~=-i, and (PQ) ~=Q~P~, is an (anti)automorphism of the algebra A which extends to matrices by mapping itself to the entries of the transpose matrix. Thus, for example, the exact sequence (5) of right D-modules of columns in Section 3 is replaced with the exact sequence
Al-1
·
 ~ R0
®
A l0®
 ~ N
=coker(·
 ~ R0
)®0
of left D-modules of lines, for the purpose of explicit calculations.

References

[1]
Kashiwara (Masaki). -- Algebraic study of systems of partial differential equations. Mémoires de la Société Mathématique de France, n°63, 1995. -- Japanese translation of the author's thesis (1970). xiv+72p.

[2]
Malgrange (Bernard). -- Systèmes différentiels à coefficients constants. In Séminaire Bourbaki, Vol. 8, pp. 79--89. -- Société Mathématique de France, Paris, 1995. Exposé n°246.

[3]
Oberst (Ulrich). -- Multidimensional constant linear systems. Acta Applicandae Mathematicae, vol. 20, n°1-2, 1990, pp. 1--175.

[4]
Palamodov (V. P.). -- Linear differential operators with constant coefficients. -- Springer-Verlag, New York, 1970. viii+444 pages.

[5]
Polderman (Jan Willem) and Willems (Jan C.). -- Introduction to mathematical systems theory. -- Springer-Verlag, New York, 1998. A behavioral approach. xxx+424 pages.

[6]
Pommaret (J. F.) and Quadrat (A.). -- Generalized Bézout identity. Applicable Algebra in Engineering, Communication and Computing, vol. 9, n°2, 1998, pp. 91--116.

[7]
Pommaret (J. F.) and Quadrat (A.). -- Algebraic analysis of linear multidimensional control systems. IMA Journal of Mathematical Control and Information, vol. 16, n°3, 1999, pp. 275--297.

[8]
Pommaret (J. F.) and Quadrat (A.). -- Localization and parametrization of linear multidimensional control systems. Systems & Control Letters, vol. 37, n°4, 1999, pp. 247--260.

[9]
Pommaret (J. F.) and Quadrat (A.). -- Formal elimination for multidimensional systems and applications to control theory. Mathematics of Control, Signals, and Systems, vol. 13, n°3, 2000, pp. 193--215.

[10]
Pommaret (J. F.) and Quadrat (A.). -- A functorial approach to the behaviour of multidimensional control systems. In The Second International Workshop on Multidimensional (nD) Systems (Czocha Castle, 2000), pp. 91--96. -- Tech. Univ. Press, Zielona Góra, 2000.

[11]
Quadrat (Alban). -- A fractional representation approach of synthesis: an algebraic analysis point of view. SIAM Journal on Optimization and Control. -- To appear.

[12]
Quadrat (Alban). -- Analyse algébrique des systèmes de contrôle linéaires multidimensionnels. -- Thèse de doctorat, École nationale de Ponts et Chaussées, September 1999.

[13]
Spencer (D. C.). -- Overdetermined systems of linear partial differential equations. Bulletin of the American Mathematical Society, vol. 75, 1969, pp. 179--239.

[14]
Wood (Jeffrey). -- Modules and behaviours in nd systems theory. Multidimensional Systems and Signal Processing, vol. 11, n°1-2, 2000, pp. 11--48. -- Recent progress in multidimensional control theory and applications.

This document was translated from LATEX by HEVEA.