1 Balancing-Related Model Reduction for Large-Scale Unstable Systems

By Peter Benner.

Model reduction is an increasingly important tool in analysis and simulation of dynamical systems, control design, circuit simulation, structural dynamics, CFD, etc. In the past decades many approaches have been developed for reducing the order of a given model. Here, we will focus on balancing-related model reduction techniques that have been developed since the early 80ies in control theory. The mostly used technique of balanced truncation (BT) [?] applies to stable systems only. But there exist several related techniques that can be applied to unstable systems as well. We are interested in techniques that can be extended to large-scale systems with sparse system matrices which arise, e.g., in the context of control problems for instationary partial differential equations (PDEs). Semi-discretization of such problems leads to linear, time-invariant (LTI) systems of the form

\begin{aligned}ẋ(t) & = & Ax(t) + Bu(t), \\ y(t) & = & Cx(t) + Du(t), \end{aligned}  (1)

where A ∈ ℝ^{n×n}, B ∈ ℝ^{n×m}, C ∈ ℝ^{p×n}, D ∈ ℝ^{p×m}, and x^{0} ∈ ℝ^{n}. Here, n is the order of the system and x(t) ∈ ℝ^{n}, y(t) ∈ ℝ^{p}, u(t) ∈ ℝ^{m} are the state, output and input of the system, respectively. We assume A to be large and sparse and n ≫ m, p. Applying the Laplace transform to (??) (assuming x(0) = 0), we obtain

Y (s) = (C(sI − A)^{−1}B + D)U(s) =: G(s)U(s),

where s is the Laplace variable, Y, U are the Laplace transforms of y, u, and G is called the transfer function matrix (TFM) of (??). The TFM describes the input-output mapping of the system. The model reduction problem consists of finding a reduced-order LTI system,

\begin{aligned}˙x̂(t) & = & Âx̂(t) + B̂u(t), \\ ŷ(t) & = & Ĉx̂(t) + D̂u(t), \end{aligned}  (2)

of order r, r ≪ n, with the same number of inputs m, the same number of outputs p, and associated TFM Ĝ(s) = Ĉ(sI − Â)^{−1}B̂ + D̂, so that for the same input function u ∈ L_{2}(0, ∞; ℝ^{m}), we have y(t) ≈ ŷ(t) which can be achieved if G ≈ Ĝ in an appropriate measure. If all eigenvalues of A are contained in the left half complex plane, i.e., [??) is stable, BT is a viable model reduction technique. It is based on balancing the controllability and observability Gramians W_{c}, W_{o} of the system (??) given as the solutions of the Lyapunov equations

AW_{c} + W_{c}A^{T} + BB^{T} = 0,  A^{T} W_{o} + W_{o}A + C^{T} C = 0.  (3)

Based on W_{c}, W_{o} or Cholesky factors thereof, matrices V, W ∈ ℝ^{n×r} can be computed so that with

Â := W^{T} AV, B̂ := W^{T} B, Ĉ := CV, D̂ = D,

the reduced-order TFM satisfies

σ_{r+1} ≤ ∥G − Ĝ∥_{∞} ≤ 2 ∑_{k=r+1}^{n} σ_{k},  (4)

where σ_{1} ≥ … ≥ σ_{n} ≥ 0 are the Hankel singular values of the system, given as the square roots of the eigenvalues of W_{c}W_{o}. The key computational step in BT is the solution of the Lyapunov equations (??). In recent years, a lot of effort has been devoted to the solution of these Lyapunov equations in the large and sparse case considered here. Nowadays, BT can be applied to systems of order up to n = 10^{6}, see, e.g., [?, ?]. Less attention has been payed so far to unstable systems, i.e., systems where A may have eigenvalues with nonnegative real part. Such systems arise, e.g., from semi-discretizing parabolic PDEs with unstable reactive terms. We will review methods related to BT that can be applied in this situation and discuss how these methods can also be implemented in order to become applicable to large-scale problems. The basic idea of these methods is to replace the Gramians W_{c} and W_{o} from (??) by other positive semidefinite matrices that are associated to (??) and to employ the algorithmic advances for BT also in the resulting model reduction algorithms.

References

[1] P. Benner, V. Mehrmann, and D. Sorensen, editors. Dimension Reduction of Large-Scale Systems, volume 45 of Lecture Notes in Computational Science and Engineering. Springer-Verlag, Berlin/Heidelberg, Germany, 2005.

[2] J.-R. Li and J. White. Low rank solution of Lyapunov equations. SIAM J. Matrix Anal. Appl., 24(1):260–280, 2002.

[3] B. C. Moore. Principal component analysis in linear systems: Controllability, observability, and model reduction. IEEE Trans. Automat. Control, AC-26:17–32, 1981.