Brief description

StabNd is a maple library for analyzing the stability and the stabilisation of several kind of dynamical systems (multidimensional discrete linear systems, differential time-delay systems, fractional systems, systems with parameters).

The analysis of stability and stabilisation is at the core of the study of these systems and are considered so far to be challenging problems in control theory community.

This library developes an algebraic framework for handling these problems where systems are considered in the frequenty domain (e.g. fractional representation approach). Thus, StabNd strongly relies on classical symbolic methods for solving algebraic system of equations and more generally on methods from real algebraic geometry (Grobner bases, univariate parametrization, critical points methods, descriminant varieties...).

In the StabND library, the emphasis is put on certified methods. Namely, provided that the input (the system) is given in an exact form, we require that the output of our algorithms is mathematically correct.

The library consists of two distinct parts. The first one is dedicated to the study of multidimensional linear discrete systems ($n$-D systems). The seconde one is dedicated to the study of differential time-delay systems with commensurate delays.

Multidimensional linear discrete system

Multidimensional or n-D systems (Bose (1984)) are systems in which information propagates in more than one independent direction (usually the time axis for standard 1-D systems). Multidimensional systems naturally arise in the study of partial difference equations, differential time-delay systems, partial differential equations, images processing,filters.

A fundamental structural property of such systems is the structural stability which implies that for a bounded input the system yields a bounded output. Testing this property is refered to as the stability problem.

In the absence of such a property, a fundamental problem then consists in computing a feedback control such that the resulting closed-loop system is stable. Checking the existence of (resp. computing) such a control is refered to as the internal stabilizability (resp. Stabilization) problem.

In the frequency domain, a multidimensional system is represented by a transfer matrix with entries in the ring of rational fraction in {z1,...,zn}.

Structural stability (Download sources here)

An n-D system is said to be structurally stable if the determinant of its transfer matrix has no pole in the unit polydisc. Starting from this standard characterization, our approach transforms the problem of testing the existence of pole in the polydisc into that of deciding the existence of real zero in some algebraic or semi-algebraic sets. Then, stateof- the-art real algebraic geometry techniques are used for this purpose.

Unlike the existing numerical counterparts, this new approach is not conservative. Moreover, our approach shows good practical performances for relatively small dimensions n.

StabNd proposes three different routines for analyzing the stability of n-D systems.

• IsStable

  This routine takes as input a polynomial defining the denominator of a transfer function and returns true if this polynomial has no zeros in the polydisc and false otherwise.
  
  The following table shows the average running times in secondes for "IsStable" on random polynomials in 2 and 3 variables with rational coefficients (The experiments have been conducted on 1.90 GHz 3-Core Intel i3-3227U with 3MB of L3 cache under Linux platform). The two running time columns correspond to the two variants of our routine "IsStableCAD" and "IsStableCRIT" (depending on the method used for testing the emptiness of a real algebraic set).
  
  

  
  

  
  
  

• 2dIsStable

  This routine is a variant of the previous one dedicated to the case of two-dimensional systems. Compared to the general routine, substantial improvements with respect to practical efficiency are obtained, using state-of-the-art algorithms developed in the PHD thesis of Bouzidi for the computation of the solutions of bivariate algebraic systems of equations.
  
  The following Table shows some computation times (in secondes) of the routine 2dIsStable, run on a set of danse polynomials of differents degrees
  
  

  
  

  
  
  

• WhereIsStable

  Given a two-dimensional system that depends on a set of k real parameters, this routine computes regions of the parameter's space R^k where the underlying system (after substituting the parameters) is stable. An illustrative example is given in the following.
  
  Consider a 2D system whose the transfer function has the following denominator which depends on two parameters u1 and u2:
  
  D(z1,z2) = (4u1 + 2u2 + 3)z1 + (-2u1 + 1)z2 + (4u1 - 2u2 - 2)z1*z2 + (2u1 - 2u2 + 4)z1^2*z2 + (-u1 - u2 + 1)z1*z2^2
  
  The following figures output by the routine "WhereIsStable" shows a cylindrical decomposition of the parameter space into cells in which the system is either stable or unstable. After easy processing, it turns out that 118 of these regions correspond to unstable systems.
  
  

  
  

  
  
  and after a zoom on a specific region
  
  

  
  

  
  
  

Stabilization (Download sources here)

Within the fractional representation approach, a multidimensional system can be studied by means of matrices with entries in the integral domain of structurally stable rational fractions, namely the ring of rational functions which have no poles in the closed unit polydisc.

It is known that the internal stabilizability of a multidimensional system can be investigated by studying a certain polynomial ideal I = {p1,...,pn} that can be explicitly described in terms of the transfer matrix of the plant. More precisely the system is stabilizable if and only if this ideal has no zero in the polydisc. Moreover, computing a polynomial in I that is stable (has no zeros in the polydisc), allows the effective computation of a stabilizing controller (see [B. Quadrat, Cluzeau, 19]). It should be stressed that these two questions are known to be open problems since the 70's.

In the library StabND, so far, only the class of n-D systems for which the ideal I is zero-dimensional is considered (this includes the class of 2-D systems). We list in the following, the available routines regarding to the study of the stabilization of n-D systems.

• IsStabilizable

  This routine takes as input a zero-dimensional polynomial ideal and return true if the ideal has no zero lying in the polydisc and false otherwise.

• StablePolynomial

  This routine compute a stable polynomial vanishing on a 0-dimensional algebraic set that has no zero inside the polydisc.
  

The use of the two previous routines is illustrated in the following example

Consider a 2D system given by the following transfer function

P=N/D = (z1^2-2z1-2)/(z1+z2-2)

We would like to compute (if it exists) a control of the form C = X/Y such that the closed-loop system is stable, which means that 1+CP is stable. In other words, we are seeking for two polynomials X, Y in Q[z1,z2] such that the polynomial s = X*N+Y*D is stable.

The first routine, i.e., "IsStabilizable" output "true". This shows that the the two polynomials N and D do not have common zero in the polydisc.

The second routine i.e., "StablePolynomial" output the polynomial s(z1,z2)= z1*z2-3z1-3z2+8. One can check that this polynomial is stable using for example the routine "IsStable" described above.

The following figure shows the stable polynomial obtained by an exact factorization in dots, the approximate factorization used in our algorithm in dash, and Finally the stable polynomial s obtained after adding the correcting term represented by the solid curve.

In the following table, we report the running times (in seconds) of IsStabilizable and StablePolynomial applied to systems of randomly chosen polynomials in two or three variables with integer coefficients chosen uniformly at random between -100 and 100. One can notice that, in general, the running times of IsStabilizable are higher than those of StablePolynomial.

Differential time-delay systems with commensurate delays

Linear time-invariant differential systems with commensurate time delays are given by a state-space representation of the form . In the frequency domain, such systems have characteristic functions defined by quasipolynomials of the form .

StabND proposes a set of routines to compute with quasipolynomials. In particular, this routines allow to analyze various notion of stability of the time delay systems. For example, delay-independant stability, delay dependant stability, stability for a given value of the delay.

Asymptotic stability (Download sources here)

Within the frequency-domain approach, the asymptotic stability of Differential time-delay systems with commensurate delays is ensured by the condition that all the roots of the corresponding quasipolynomial have negative real parts. Our approach for checking this condition consists in computing the set of critical zeros of the quasipolynomial, i.e., the roots (and the corresponding delays) of the quasipolynomial that lie on the imaginary axis, and then analyzing the variation of these roots with respect to the variation of the delay. Following this approach, based on solving algebraic systems techniques, our implementation proposes a certified and efficient symbolic-numeric algorithm for computing the set of critical roots of a quasipolynomial. It also proposes a routine for the computation of Puiseux series at a critical zeros which allow us to finely analyze the stability of the system with respect to the variation of the delay

StabNd proposes the following routines for analyzing the stability of time-delay systems with commensurate delays.

• CriticalPairs

  This routine takes as input a quasipolynomial and return a symbolic representation as well as certified numerical approximations for its critical pairs.

• IsDelayIndStable

  This routine takes as input a quasipolynomial and return true if the corresponding system is asymptotically stable independently of the delay.

• StabilityAtCritical

  This routine analyzes the stability around a critical pair. More precisely, it output the way the stability behaves under small variation of the delay.

• ForwhichDelayStable

  This routine compute the values of the delays for which the system is stable. This routine follows the algorithme described in [B. Poteaux, Quadrat 17]