Effective Algebraic Analysis in Linear Control Theory

Effective Algebraic Analysis in Linear Control Theory

Alban Quadrat

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:

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.
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].
Differential-delay systems with constant delays are a generalization common to Kalman systems and polynomial systems by introducing the constant-delay operators d_i defined by (d_if)(t)=f(t-t_i) for some real t_i. The generalized forms are

.

x

(t)=

r

å

i=0
A_ix(t-t_i)+B_iu(t-t_i), y(t)=

r

å

i=0
C_ix(t-t_i)+D_iu(t-t_i),
and
P(d/dt,d₁,...,d_r)y+Q(d/dt,d₁,...,d_r)u=0,
respectively. A typical occurrence of delay is when transmitting a signal u through a channel.
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

æ
è

0	A-d/dt Id	B
Id	C	D

ö
ø

and R=

(

)

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 F^k denote the algebra of functions in k variables, and consider a differentiel operator D from F^m to F^l (of finite order). Given hÎ Fⁿ, the necessary conditions for the existence of xÎ F^m such that Dx=h are called compatibility conditions of D; they take the form D₁h=0 for some differential operator D₁. Writing D₀=D, we have D₁°D₀=0. When D₁ encapsulates all compatibility conditions, the sequence

F^m

D₀

F^l₀

D₁

F^l₁

of differential operators is called formally exact (at F_l₀). Formally exact sequences can always be extended (to the right) into longer sequences, so that denoting the solution set of D=D₀ in F^m by Q, we obtain a formally exact sequence

0®Q® F^m

D₀

F^l₀

D₁

F^l₁

D₂

F^l₂®···

(at Q and each F^l_k) 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 F^l_n=0 from some n on, by exhibiting a canonical, formally exact sequence

0®Q=kerD₀® F^m

D₀

F^l₀

D₁

F^l₁

D₂

F^l₂®···

D_r

F^l_r®0 (2)

called the Janet sequence of D, in which each (non-zero) D_i 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 D_i as defined by an l_i× l_i-1 matrix R_i of multivariate linear differential operators in

A=R(x₁...,x_r)[¶₁,...,¶_r].

(We set l_-1=m.) In terms of matrices,

D_i=R_i·=(x|® R_ix),

so that R_i+1R_i·=0. We then consider the maps · R_i from A^l_i to A^l_i-1, whose elements are viewed as row vectors. To start with, the map · R₀ defines an algebraic representation of a generic solution x the PDE system D₀x=0 in the following way. Let (e₁,...,e_m) be the canonical basis of A^m and consider the maps

0¬ M=A^m/A^l₀R₀

A^m

· R₀

A^l₀, (3)

where p denotes the canonical projection p(v)=v+A^l₀R₀. The cokernel

M=coker(· R₀)=A^m/A^l₀R₀

of · R₀ contains the announced generic solution: setting

x_i=p(e_i)=e_i+A^l₀R₀,

we get D₀x=x R₀=0. Other members of M correspond to linear combinations of the x_i and their derivatives, i.e., to the observables defined above. We now proceed to follow up with the next D_i's. A sequence

L''

of linear maps (between modules) is said to be exact (at L') if im u=kerv. (Thus (3) is exact at M and A_l₀.) It can be shown that any Janet sequence (2) gives rise to the exact sequence

0¬ M

A^m

· R₀

A^l₀

· R₁

A^l₁

· R₂

A^l₂¬···

· R_r

A^l_r¬0 (4)

(at M and each A^l_k). Here, · R_i+1R_i=0 by exactness. Since A has no zero divisor, this means that R_i+1R_i=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(· R₀)), then the obstruction of kerp to be free (as the module ker(· R₀)=im(· R₁)), etc. (A module is called free when it is isomorphic to some A^r, 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:F^l_-1® F^l₀

whose compatibility conditions are described by D=D₀, i.e., to look for a formally exact sequence

F^l_-1

D_-1

F^l₀

D₀

F^l₁.

In this situation, for any xÎ F^l₀ the existence of pÎ F^l_-1 satisfying D_-1p=x is equivalent to the fact that x solves the differential equation D₀x=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 ò₀^tF(t) dt of an observable F of some system D₀. The optimization problem is then to minimize over all tuples x=(y,x,u)^T of functions constrained by D₀x=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 ò₀^tG(t) dt 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

A^l_-1

R₀·

A^l₀® N=coker(R₀·)=A^l₀/R₀A^l_-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 hom_A(L,A) of A-linear applications from L to A. Correspondingly, any linear map L

L' induces a map from the dual of L' to the dual of L: to lÎhom_A(L',A), one associates l° uÎhom_A(L,A). This takes a simple form when the modules are free and of finite rank (i.e., L=A^m and L'=A^l, 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 µÎhom_A(A^k,A) are defined by their values on the canonical basis (e_i) of A^k by

µ=·

(

µ(e₁),...,µ(e_k)

)

^T,

so that the dual of A^k is isomorphic to A^k (now viewed as a right module of column vectors). In this setting, the dual of a map A^m

· U

A^l is A^m

U·

A^l. 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

A^l_-2

R_-1·

A^l_-1

R₀·

A^l₀ ® N®0.

An algorithm for this purpose will be given in Section 5. By dualization (i.e., application of the hom_A(·,A) functor), it becomes a sequence

A^l_-2

· R_-1

A^l_-1

· R₀

A^l₀ ¬hom_A(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(· R₀). Upon forgetting the map · R₀ and prolonging · R_-1 into

A^l_-2

· R_-1

A^l_-1

· R'₀

A^l'₀,

we obtain an ``exact'' representation of ker(· R_-1) as im(· R'₀). It can be proved that the quotient

im(· R'₀)/im(· R₀)Í 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'₀ (that are elements of im(· R'₀)), viewed modulo im(· R₀).

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·

A^l_-n

R_-n+1·

···

R_-2·

A^l_-2

R_-1·

A^l_-1

R₀·

A^l₀ ® 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

A^l_-n

· R_-n+1

···

· R_-2

A^l_-2

· R_-1

A^l_-1

· R₀

A^l₀ ¬hom_A(N,A)¬0 (7)

of left D-modules that, again, is usually no longer exact. By dropping hom_A(N,A) from (7), we obtain another non-exact sequence, but of free modules only,

···

· R_-n

A^l_-n

· R_-n+1

···

· R_-2

A^l_-2

· R_-1

A^l_-1

· R₀

A^l₀ ¬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

ext_Aⁱ(N,A)=ker(· R_-i)/im(· R_-i+1)

for extension modules (with in particular ext_A⁰(N,A)=ker(· R₀)=hom_A(N,A)).

The nullity or non-nullity of the extⁱ'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®hom_A

(

hom_A(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:

M is torsion-free if and only if ext_A¹(N,A)=0;
M is reflexive if and only if ext_A¹(N,A)=ext_A²(N,A)=0;
M is projective if and only if ext_A¹(N,A)=...=ext_A^r(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®A^p₁®A^p₂ ®...®A^p_r

if and only if ext_Aⁱ(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[¶₁,...,¶_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(x₁...,x_r)[¶₁,...,¶_r],

introduce the two left D-modules M=coker(· R) and N=coker(R·) of the maps between the free modules A^m and A^l. Then:

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;
M is torsion-free if and only if ext_A¹(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;
M is reflexive if and only if ext_A¹(N,A)=ext_A²(N,A)=0;
in the event R has constant coefficients and full row module, and if
ext_A¹(N,A)=...=ext_A^r-1(N,A)=0 while ext_A^r(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;
M is projective if and only if
ext_A¹(N,A)=...=ext_A^r(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;
if M is free, the control system is flat and has direct and inverse generalized Bézout identities.

Further intermediate situations, ext_A¹(N,A)=...=ext_A^k-1(N,A)=0 and ext_A^k(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 A^m

· R

A^l into an exact sequence A^m

· R

A^l

· S

A^k is done in the following fashion. Let (e₁,...,e_m) and (f₁,...,f_l) be the canonical bases of A^m and A^l, respectively, and denote the ith row of R=(r_i,j) by h_i. Thus h_i=å_j=1^mr_i,je_j. Prolonging the map amounts to finding non-trivial relations å_i=1^ls_ih_i=0. Now introduce the submodule Z of A^m+l generated by the formal linear combinations f_i-h_i. We contend that computing a Gröbner basis for this module and for a term order that eliminates the e_i results in linear combinations å_i=1^ls_if_iÎ Z, each of which corresponds to a relation between the h_i. Additionally, any relation can be obtained as a linear combination of the relations thus obtained.

In effect, consider an element z=å_i=1^ls_if_iÎ Z; thus å_i=1^ls_ih_i is in Z and is a combination å_i=1^ll_i(f_i-h_i), which is only possible, in view of the coefficients of the f_i, if the l_i are zero, thus if å_i=1^ls_ih_i=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 e_i, it suffices to consider each of those k elements as a row, and to glue them in column to obtain a new matrix S=(S_i,j) such that the sequence A^m

· R

A^l

· S

A^k 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 x_i^~=x_i, ¶_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

A^l_-1

R₀

^l₀®

=coker(·

R₀

)®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 L^AT_EX by H^EV^EA.