Structural Stability of Multidimensional Discrete Linear Systems

Problem Definition

A multidimensional discrete linear system defined by a multivariate rational transfer function \(G\) is said to be structurally stable if the denominator \(D\) of \(G\) has no zeros in the complex unit polydisc \(\mathbb{U}^n\): \(\mathbb{U}^n = \prod_{k=1}^{n} \{z_k \in \mathbb{C} \, | \, |z_k| \leq 1\}.\)

Reformulation of the Problem

Using results from DeCarlo (1977), the stability condition can be checked through the following conditions:

  • Each univariate polynomial \(D(z_k,1,\dots,1)\) must have no roots in \(|z_k| \leq 1\) for all \(k = 1, \dots, n\).

  • The multivariate polynomial \(D(z_1,\dots,z_n)\) must have no roots on the torus \(|z_1| = \dots = |z_n| = 1\).

The first condition can be checked using signed subresultant (Sturm-Habicht) sequences. The second condition is transformed into a real algebraic problem using a Möbius change of variables: \((z_k = \frac{x_k - i}{x_k + i},\) leading to a system \(\{\mathcal{R} = 0, \mathcal{I} = 0\}\) with real polynomials \(\mathcal{R}, \mathcal{I} \in \mathbb{R}[x_1, \dots, x_n]\).

Parametric Case

When \(D\) depends on parameters \(U_1, \dots, U_l\), the goal is to determine for which parameter values the system remains structurally stable. The approach follows:

  1. Compute the Discriminant Variety (DV)

    • The discriminant variety \(DV\) of the system \(\{\mathcal{R} = 0, \mathcal{I} = 0\}\) with respect to the parameter space projection is computed.

  2. Construct a Cylindrical Algebraic Decomposition (CAD)

    • A CAD of \(\mathbb{R}^l\) adapted to \(DV\) is computed.

    • Cells of maximal dimension are identified.

  3. Sample and Solve

    • A rational sample point is selected in each cell.

    • The polynomial system is solved at each sample point to determine stability.

  4. Lienard-Chipart Criterion

    • Additional stability conditions are derived for the univariate polynomials \(D(z_1,1)\) and \(D(1,z_2)\) using the Lienard-Chipart criterion.

Implementation in PACE.jl

To implement this method in PACE.jl:

  • DiscriminantVariety.jl computes the discriminant variety.

  • lienard_chipart() provides additional stability conditions.

  • PACE.jl functions are used for sampling in CAD cells.

  • RationalUnivariateRepresentation.jl and RS.jl solve polynomial systems.

  • Nemo.jl is used for polynomial manipulations.

The full implementation is wrapped in the function stability_parametric().

begin
    import Pkg
    Pkg.activate();
    using PaceControl, MPFI, Nemo, AbstractAlgebra
    
end

Example of transfer function depending on two parameters

begin
    Rc, (z1,z2,u1, u2) = polynomial_ring(Nemo.ComplexField(), ["z1", "z2", "u1", "u2"])
    
    D = u2*z1*z2 - u1*z2 - u2*z1 + z1*z2 - z1 + 1
end
z1*z2*u2 + z1*z2 - 1.0000000000000000000*z1*u2 - 1.0000000000000000000*z1 - 1.0000000000000000000*z2*u1 + 1 
stable, unstable = stability_parametric(D)

(Any[Rational{BigInt}[0, -1]], Any[Rational{BigInt}[-7//2, -11//4], Rational{BigInt}[-7//2, -1], Rational{BigInt}[-7//2, 3//4], Rational{BigInt}[-2, -2], Rational{BigInt}[-2, -1], Rational{BigInt}[-2, 0], Rational{BigInt}[0, -2], Rational{BigInt}[0, 0], Rational{BigInt}[3//2, -11//4], Rational{BigInt}[3//2, -1], Rational{BigInt}[3//2, 3//4]])
stable 
1-element Vector{Any}:
 Rational{BigInt}[0, -1]
unstable 
11-element Vector{Any}:
 Rational{BigInt}[-7//2, -11//4]
 Rational{BigInt}[-7//2, -1]
 Rational{BigInt}[-7//2, 3//4]
 Rational{BigInt}[-2, -2]
 Rational{BigInt}[-2, -1]
 Rational{BigInt}[-2, 0]
 Rational{BigInt}[0, -2]
 Rational{BigInt}[0, 0]
 Rational{BigInt}[3//2, -11//4]
 Rational{BigInt}[3//2, -1]
 Rational{BigInt}[3//2, 3//4]