Linear Methods

From Model order reduction site at MIT

Contents 1 Introduction 2 Model reduction for LTI systems 3 LTI model reduction methods roadmap 3.1 Projection-based model reduction methods 4 Overview of projection-based methods 5 References

Introduction

Model Order reduction techniques for linear dynamical systems are developed rather properly, though there are still quite a lot of issues to address.

First of all, the linear model reduction techniques usually deal with linear time-invariant (LTI) systems. There exist methods for linear time-varying systems as well (for example see ^[1] and references therein).

Discrete-time and continuous-time systems. Based on the nature of the time variable, all dynamical systems are divided into the continuous time (CT) and discrete-time (DT) sytsems. We do not plan to consider discrete-time sytems and problems associated with DT model reduction in detail (though, we will definitely say a couples of words). If you want us to write about DT model reduction in more detail, please let us know. Therefore in all subsequent notes we will mutually assume the continuous-time system (if not mentioned otherwise).

Model reduction for LTI systems

When we speak about reducing CT LTI system, people usually think about the state-space realization, i.e. the description of a system in the form of a differential equation:

Here vector x(t) is referred as a state (and the corresponding n-dimensional space is called state space), u(t) is a vector-valued input, y(t) is a vector-valued output. The dimensionality n of the state vector is called an order of a system. m is the number of inputs, and l is the number of outputs. The matrix A of size n×n is called system matrix, the matrices B and C of sizes 'n×m and l×n are termed input and output matrices respectively. As a short-hand notation, the form (1) is termed (A, B, C, D). If matrix D is zero, then such form is termed (A, B, C).

Quite frequently it happens that it's more favourable to describe the system not in the form (1), but in another form:

This form is usually referred to as generalized state-space form, or a descriptor form. The matrix E of size n×n is called a descriptor matrix, and corresponding short-hand notation is (E, A, B, C, D). If the matrix E is invertible, the system (2) is equivalent to the system (E^-1A, E^-1B, C, D) in the form (1). However, if the matrices E and A are sparse, E^-1A may be dense, therefore it's beneficial to keep the system description in the form of a generalized state-space (2) and not convert it into the form (1). If the descriptor matrix E is singular, the system (2) becomes the set of algebraic-differential equations, and such system, in general, cannot be converted to (1). The model reduction for the systems in the descriptor form is considered in, for example, ^[2] and ^[3].

However, one should note that state-space descriptions (1) or (2) by no means are able to represent any CT LTI system! For example, ideal delay (the system that just represents a delayed input) cannot be represented in the state-space form at all. In applications, we are usually approximating real-life LTI systems by the systems in the form (1) or (2). Currently these state-space forms are the most widely used descriptions for representing any LTI system because of their manageability. Researchers have considered other kinds of descriptions, for example, in the form of delay-differential equations, however such kind of systems are much more difficult to analyze.

The goal of the model order reduction. Let's assume that we have the system description in the form (1) or (2) and the order of the system n is very big - for example, hundreds or thousands. Such kind of descriptions can be obtained, for example, by discretization of some device.

Since cost of transient (time-domain) simulation of such system is proportional to n³(if the system is dense and general, less if it is sparse or fast solver exists), it's very inefficient to simulate this system, especially if it is being simulated as a part of a larger system. If the number of input and output signals is small, (l << n, m << n), one may think that there is a lot of redundancy in the large model, that is, input-output relationships of this system can be approximated quite accurately with the system having much lower order.

The goal of the model order reduction is: given a large system in the form (1) or (2), to provide another state-space system in the same form (1) or (2), but of lower order q << n, which approximates (in some sense) input-output relationships for the original system.

LTI model reduction methods roadmap

MOR methods for LTI systems fall into two major groups:

1. Projection-based methods
2. Non-projection based methods

The first group consists of such methods as Krylov-subspace (moment matching methods), Balanced-truncation method, Proper Orthogonal Decomposition (POD) methods etc.

The second group consists of such methods as Hankel optimal model reduction, singular perturbation method, various optimization-based methods etc.

Projection-based model reduction methods

The vast majority of model reduction methods are projection-based. These methods share one common feature: they are trying to find such q-dimensional subspaces S₁ and S₂ of the state space such that the reduced system will be the result of projection of the state onto S₁ and residual onto S₂; considering the system in the form (E, A, B, C, D) and picking matrices W and V of sizes n×q spanning S₁ and S₂ respectively:

This results in the state-space system (E_r, A_r, B_r, C_r, D), where

(the subscript r denotes the reduced model). If the initial system was in the form (1), then E=I ( n×n identity matrix), and matrices W and V are enforced to be biorthogonal, that is, W^TV = I.

The following important theorem holds ^[4]: The input-output properties of the reduced system in (3) depend only on the column spans of W and V, that is, only on the choice of projection subspaces S₁ and S₂.

If subspaces S₁ and S₂ are the same, such projection method is called orthogonal, otherwise it's called oblique.

Overview of projection-based methods

All projection-based methods fall into the following major types based on the method of obtaining projection subspaces:

1. Krylov-subspace (moment-matching) - based methods
2. Balanced realization (or SVD) - based methods
3. Proper orthogonal decomposition (POD) -based methods

Methods from the first group obtain their projection subspaces as the Krylov subspaces of the matrices and

Methods from the second group obtain their projection subspaces as the dominant eigenspaces of products of controllability and observability Gramians P and Q.

Methods from the third group obtain their projection subspaces from the snapshots of the states that the system passes when simulating some training input .

An overview of projection-based methods for LTI systems can be found in ^[5].

References

1. ↑ H. Sandberg, A.Rantzer, "Balanced truncation of linear time-varying systems", IEEE Transactions on Automatic Control, v. 49, No. 2, pp. 217-229
2. ↑ Stykel T. "Analysis and numerical solution of generalized Lyapunov equations". Ph.D. thesis, Institut fur Mathematik, Technische Universitat Berlin, 2002
3. ↑ Mehrmann, V., Stykel, T. "Balanced truncation model reduction for large-scale systems in descriptor form". In Dimension Reduction of Large-Scale Systems, Lecture Notes in Computational Science and Engineering, Vol. 45, pp. 83-115, Springer-Verlag, 2005
4. ↑ Jing Rebecca Li, "Model Reduction of Large Linear Systems via Low Rank System Gramians," Ph.D. thesis, Massachusetts Institute of Technology, 2000.
5. ↑ A. Antoulas,"A survey of model order reduction methods for large-scale systems"