搜档网
当前位置:搜档网 › Efficient Balance-and-Truncate Model Reduction for Large Scale Systems

Efficient Balance-and-Truncate Model Reduction for Large Scale Systems

Purdue University

Purdue e-Pubs

ECE Technical Reports

Electrical and Computer Engineering

11-1-2000

Efficient Balance-and-Truncate Model Reduction for Large Scale Systems

Venkataramanan Balakrishnan

Purdue University School of Electrical and Computer Engineering

Qing Su

Purdue University School of Electrical and Computer Engineering

Cheng-Kok Koh

Purdue University School of Electrical and Computer Engineering

This document has been made available through Purdue e-Pubs, a service of the Purdue University Libraries. Please contact epubs@https://www.sodocs.net/doc/559021143.html, for additional information.

Balakrishnan, Venkataramanan; Su, Qing; and Koh, Cheng-Kok, "Efficient Balance-and-Truncate Model Reduction for Large Scale Systems " (2000).ECE Technical Reports.Paper 31.https://www.sodocs.net/doc/559021143.html,/ecetr/31

E F F I C I E N T B ALANCE-AND-

T RUNCATE M ODEL R EDUCTION FOR L A R G E S CALE S YSTEMS

TR-ECE 00-15

N O V E M B E R 2000

Efficient Balance-and-Truncate Model Reduction for Large Scale

Systems

Venkataramanan Balakrishnan

Qing Su

Cheng-Kok Koh

School of Electrical and Computer Engineering

Purdue University

West Lafayette, IN 47907-1285

Abstract

We present efficient implement a t i ons of the balance- and-truncate model reduction technique for large-scale systems. The key observation that distinguishes our ap- proach is that Krylov subspace methods (Arnoldi and Lanczos) directly yield approximate low-rank square roots1 of the system Gramians; the balancing transformation can be then constructed from these square roots, obvi- ating the need for solving any Lyapunov equations. In addition, the order of the reduced model is not fixed a priori as with some existing methods, but is determined from the problem data. Numerical simulations show t,hat our approach performs very well over a range of exam- ples, and offers considerable savings in practice.

'We use the term "square root" to mean the not necessarily symmetric square root of a matrix: If M= = N N T,we say N is the square root of M.

1 Introduction

As engineering

Our objective is to present efficient algorithms for the model reduction of large-scale linear time-invariant (LTI) state-space models.

Model reduction of LTI systems is a well-studied topic. One approach is to expand the transfer function as a power series around a suitable point in the complex plane, and obtain a lower order model whose power series coefficients match the first few original coefficients ("moment-matching"). A well-known example of such an approach is Pad6 approximation, which can be shown to be optimal in a certain sense. Another model-reduction approach involves truncating the state space to the principal controllable subspace, or the principal observable subspace. Ilrell-conditioned and efficient implementation of these two techniques has been the subject of considerable investigation. Model reduction through moment-matching is the subject of the asymptotic waveform evaluation (AWE) technique due to Huang, Pillage. and Rohrer

discussion of the numerical properties of these algorithms can be found in

-order model can be then obtained by projecting the state-space on these subspaces

(This is the so-called balanced realization.) In the balanced coordinates, state variables are ordered by the ease with which they are simul- taneously reachable from the input and observable from the output. Thus, state-variables that are not easy to reach and not easily observed can the omitted (or the model truncated). An attractive feature of the balance-and-truncate method is that the approximation error can be shown to be bounded

size eigen-decomposition. One approach towards addressing this issue is to obtain low-rank approximate solutions to the large-size Lyapunov equations, for instance, the "Alternate

a nd its modifications

computation methods to first find the principal controllable or observable subspace, and then solve reduced-order Lyapunov equations to proceed with balancing and truncating; see, for example,

no Lyapunov equations need solution. The key observation is the following:

lR N,

all of its eigenvalues have negative real part, and that the realization is minimal. The objective in model reduction is to obtain another linear system

where to y well-approximated by the

Balanced truncation is one well-known model reduction scheme. The first step is to compute the con- trollability and observability Gramians, denoted respectively, and defined as

Jd e A t s s T e A T t=

w

Therefore, with the eigenvalues sorted in descending order, the eigenvectors of

can be shown to be the square of the singular values and the corresponding left singular vectors of the mapping from state x to output y. Therefore, with the eigenvalues sorted in descending order, the eigenvectors of

=X X T and

are orthogonal, and is diagonal, with

the diagonal entries in descending order. The diagonal entries of values of

the system.

Define

- 1

c, D). It

T;'B, (A,

is easily verified that the corresponding controllability and observability Gramians are

Thus, in the new state-space coordinates, the state components are as reachable from the input as they are observable at the output. Moreover, when a diagonal value of

"throwing away" state components for which the corresponding diagonal entry a; of

>

a2> a n>>

The approximation error with the balance-and-truncate model reduction is well understood, and we describe it next. The state-space realization of the reduced order model is given by (;4red,

-=

i s an N

-space realization

Then this is followed by a small-size balance-and-truncate model reduction. In contrast, the approach that we propose herein is a direct approach: We will describe algorithms that directly compute low-rank square roots of the Gramians. We will then show how these factors can be combined to yield "approximate" balancing transformations that automatically truncate the state space. The idea of computing low-rank approximations can be found in LW91]. However, these approximations

have only been used to find the (approximate) principal controllable and/or principal observable subspace, and not to find the (approximate) balanced coordinates; this is one of the distinguishing features of our work.

2.2 Approximate Balanced Truncation

We first describe the idea behind an approximate balance-and-truncate method that relies on low-rank square roots of the Gramians. (We will defer a careful analysis of the approximation error to Section 2.4.) Suppose that we have approximate low-rank square roots of the Gramians,

such that

[

Kt N x n and

diag W,.

Thus, the matrices

N, the major computational task underlying the implementation of the forementioned ap- proach is that of efficient calculation of low-rank square roots for the Gramians

- A), and we then have

Similarly, with +A)-', we have

One interpretation of these steps is that we have derived a discrete-time system with state-space real- ization (Ap, that has the same Gramians as the continuous system, using the conformal map- ping = =

+

= D -

a nd

well-conditioned computation of CT,

of the eigenvalues)

h e key here is that the eigenvalues of A and A, are related by

+ +

a good choice for p is simply

-

The implementation of the power iterations is straightforward, and

requires only matrix-vector multiplications. To implement the inverse power iterations, we began with an LU factorization of A; then every inverse power iteration required the solution of two triangular systems of linear equations.

We next discuss the Arnoldi and Lanczos iterations that compute the Krylov matrices

CT,

Ch. a nd

and k) and K(A;, CT,

and PFA;Pk =

. ..

are QR factorizations.

The algorithm Ch.

B,, CF, k) inside one iterative loop; in addition, we show explicitly the construction of

the QR factors.

. .

In the above algorithm, matrix-vector multiplications such as can be

implemented by first performing an LU factorization of +A); t hen the product

given as

, and an approximate kth order square root of CT, k) = Sk.

An nth order approximately balance-and-truncate model can be obtained through the following steps:

1. Find the SVD

2. Determine

3. Form

t

and (i.e., with = I)w ith

the Krylov matrix

P k s pans the range of the Krylov matrix

and such

that

= 4S k.

(Note that these are not QR factorizations, unlike with the Arnoldi method.)

The algorithm is:

repeat while stopping criterion is not met {

As with the Arnoldi method, we have an approximate lcth order square root of given as

given as CT,

Approximate balanced truncation can proceed as described at the end of Section 2.3.1. Note that with the Lanczos iteration

= = or the Lanczos iterations yield approximate rank-lc LU

factors for the product

Consider the error

> s o that Tr

T hus,

<_ K,P(A,)~T~

(l.Vo),

or the relative error in the approximation depends critically on the spectral radius of A,.

Finally, we may derive an expression for the error in the approximation of the

=

of X T Y.Our algorithm yields k approximate

Then,

N k

= =

Once again, the approximation error depends critically on the spectral radius of A,.

Stopping Criterion

One practical stopping criterion with both the Arnoldi and Lanczos iterations is to monitor the Frobenius norm of the product XTYk, and to stop when the change is smaller than some tolerance. The

quantity c an be computed iteratively:

The latter three terms require only matrix -vector multiplications.

Flop Counts

The flop counts of the major steps involved in the various implementations of the balance -and -truncate method are listed below. The number of states in the full -order model is N , a

nd we assume that the

Technique

3 Numerical Results

Flop count

balance -and

-truncate model reduction.

In order to illustrate the error in approximation, we consider a typical test case of a full -order model with 100 states. Our algorithm yielded a reduced -order model with 21 states. Figure

the magnitude and phase of the system response of the

Standard balance -and -truncate

I 5'

+4n 2k

+ (22 + +N 3 + (40 +

+ 2n 2

+

4n 2k

+

Original

model order 4001

I

Average flop count with the

standard balance -truncate met hod (in millions)

225 Arnoldi

23

121

46 47 105 original system, and that of the reduced -order systems, once again illustrating that the reduced -order model 107 23 obtained from our algorithms are virtually indistinguishable from those obtained by

the standard

rank approximation of the square root of the Gramian depended critically on how small the spectral radius

241

119 - A )) is. When the eigenvalues

of

can be made significantly less than one with an appropriate

choice of p. This is the reason for the remarkably good performance of our approximate balance -and -truncate schemes. For very lightly damped systems, for every choice of p,

the value of

twenty pairs of eigenvalues with a real

part of

r eveals the remarkable fact that over a large range of frequencies, our

approximate balance -and -truncate schemes perform better than the standard balance -and -truncate scheme. A possible explanation for this is that for very lightly -damped systems, the Gramians themselves

are

=

appmx~malion error

r d w d

Balanced

Arnddi -

Balanced

Lancros

I I

Standard balanced

$51

1-

m

.-. ,

I

100

400

Table 2: Comparison of flop counts. For each of our algorithms, the term "savings

"

Average flop count with the

standard balance -truncate method (in millions)

Average savings with Arnoldi Average savings with Lanczos Maximum savings with Arnoldi Maximum savings with Lanczos Minimum savings with Arnoldi Minimum savings with Lanczos

230 22 22 24 24 20 21

1900 25 25 28 26 23 23

16000 26 2 5 2 7 25 24 25

(a) Relative approximation error of 44-state reduced- (b) System response of the original 100-state

method.

(c) System response of the original 100-state lightly- (d) System response of the original 100-state

4 Conclusion

scale systems, using Krylov

methods and a small-size SVD, without the need for solving any Lyapunov equations. Numerical simulations show that our approach holds promise in the balance-and-truncate model reduction of large-scale systems.

References

-reduction techniques. IEEE Trans. Computer-Aided Design, 16(5):485-496, May 1987.

P. Feldmann and R.. W. Freund. Efficient linear circuit analysis by Pad6 approximation via the Lanczos process. IEEE Trans. Computer-Aided Design,

based on Krylov subspaces and their use in circuit simulation. Technical

E.

K. Gallivan, E.

G. Golub and C. Van Loan.

Cliffs, NJ,

P. K. Gunupudi and M. S. Nakhla. Model-reduction of nonlinear circuits using Krylov-space techniques. In Proc. 29th ACM/IEEE Design Automation Conference, pages 13-16, 1999.

I. M. Jaimoukha and E. M. Kasenally. Krylov

I.

methods. In Proc. IEEE Conf. on Decision and Control, pages 1927-1932, December 1992.

J. Li and J. White. Efficient model reduction of interconnnect via approximate system Gramians. In Proc. Int. Conf. on Computer-Aided Design, pages 380-383, 1999.

B. C. Moore. Principal component analysis in linear systems: Controllability, observability, and model reduction. IEEE Trans. Aut. Control, AC-26(1):17-32, February 1981.

1990.

相关主题