Methods in Model Order Reduction (MOR) field

LIU Zhichao

Abstract：Nowadays, the modeling of systems may be quite large, even up to tens of thousands orders. In spite of the increasing computational powers, direct simulation of these large-scale systems may be impractical. Thus, to industry requirements, analytically tractable and computationally cheap models must be designed. This is the essence task of Model Order Reduction (MOR). This article describes the basics of MOR optimization, various way of designing MOR, and gives the conclusion about existing methods. In addition, it proposed some heuristic footpath.

Key words：model order reduction (MOR);singular value decomposition (SVD);Lyapunov equations;Krylov subspace;SVD-Krylov methods;empirical gamians;trajectory-pieceWise linear (TPWL) framework

1 Introduction

Fundamental methods in the area of MOR were published in the 80s and 90s of the last century. All those methods belong to a same classification: Singular Value Decomposition (SVD). In 1990, the first Krylov subspaces related method was born (AWE). And in 1993, Feldmann proposed another method named Padé via Lanczos (PVL) as an alternative to AWE. Then, PRIMA (Passive Reduced-Interconnect Macromodel Algorithm, 1997) and recently SPRIM (Structure-Preserving Reduced-Order Interconnect Macromodeling, 2004) were developed.

More recently, a new type of methods that tries to combine the strength of SVD and Krylov based methods and avoids the pitfalls of both methods is appearing. Two main frameworks developing rapidly are namely Empirical Gamians and Trajectory-piecewise linear (TPWL) framework. As a matter of fact, usually they use Krylov method for the Krylov side of the projection and iteration technic to solve the Lyapunov equations for the SVD side of the projection.

This article describes the basics of MOR optimization, various way of designing MOR.

2 Conventional MOR methods

A linear system can be expressed by state space function:

Where: .

We want the reduced system to be presented by:

2.1 SVD-Truncated Balanced Realization (TBR)

To evaluating the systems the controllability and observability, the two gramians Wc and Wo are used. For practical reasons, one can get them by solving the two Lyapunov functions[1]:

A balanced realization is such that ,where,Wc and Wo are the gramians and σi are the Hankel singular values. Then, A can be replaced by , which has the following form:

Where: can be discarded.

By this technique, we have also the following global error bounds; r is the order of reduced model and also the dimension of :

The SVD methods have a fully automatic algorithm and an error bound, but they are computational cost and do not usually preserve the systems passivity[2].

2.2 Krylov subspace-Padé via Lanczos (PVL)

Inspired by Asymptotic Waveform Evaluation (AWE) born in 1990, the Krylov based method PVL was proposed by Feldmann as an alternative to AWE.

The order-r Krylov subspace[3] generated by an n-by-n constant matrix A and a constant vector b of dimension n is the linear subspace spanned by the images of b, that is,

The vectors , constructing the subspace are called basic vectors. By a proper choice through Lanczos procedure of two basis W and V of the Krylov subspace, so as to , one can can replace X(s) by , and we get the following expression in the Laplace (frequency) domain:

Now the transfer function of the system can be got as By the means of moment matching in the sampling points, we get a reduced order transfer function . Then the reduced model can be thus represented as:

PVL is much more computational cheap, this character allows its application in large-scale systems, but it does not always preserve stability. Another pitfall is that it is difficult to establish rigorous error bound.

Same relating improvements were developed: a Multi-input version Matrix PVL method (MPVL, multi-port version for PVL) ; another version that cures the stability problem, namely SyPVL and its multi-port version SyMPVL; besides these, recently, two-step Krylov subspace algorithm, shows much more efficiency than original ones.

Then, PRIMA (Passive Reduced-Interconnect Macromodel Algorithm, in 1997) and recently SPRIM (Structure-Preserving Reduced-Order Interconnect Macromodeling, in 2004) were developed as improvement to Krylov subspace methods using the Arnoldi procedure, note that, they are provable passivity perversion.

In the recent searches[4], by applying sampling methods for interpolation, the performance of Krylov methods can be greatly improved, these methods are called rational Krylov methods (RKM); unfortunately, the selection of these points is not an automated process. Moreover, RKM can be extended to solve non-linear or parameter-dependent problems.

2.3 SVD-Krylov methods

This type of methods tries to combine the strength of SVD and Krylov based method and avoid the pitfalls of both methods. Some of them can also be applied to nonlinear models. As a matter of fact, they use Krylov method for the Krylov side of the projection and iteration technic to solve a Lyapunov equation for the SVD side of the projection. Two major framework under studying nowadays are namely empirical gramians and Trajectory-piecewise linear (TPWL) framework methods.

2.3.1 Empirical gramians

The empirical controllability and observability gramians are as defined by Lall: At first, we need to define the empirical input gramian[5]:

where r is the number of different perturbation orientations, s is the number of different perturbation magnitudes and n is the number of inputs of the system for the controllability gramians and the number of states of the full order system for the observability gramians.

Empirical controllability gramian: Let Tp, M and Ep be given as described above, where p is the number of inputs of the system. The empirical controllability gramians for system is defined by

Where is given by

The empirical observability gramians are defined in the similar way. Thus, this method is data-driven! The method is applicable for systems for which the nonlinearities are not too severe. Another method of nonlinear system is Proper Orthogonal Decomposition (POD) method[6]. In principle, POD is to begin with an ensemble of data, collected from an experiment or other numerical procedure of a physical system. The POD is then used for producing a set of basis functions, which spans the snapshot collections.

The main drawback is that Empirical Gramians are only applicable to control-affine systems.

2.3.2 Trajectory-piecewise linear (TPWL) framework[7]

As the name of this type of methods indicates, it divides the nonlinear models into different linear pieces. And then by applying the Krylov subspace or SVD-based methods, we can get the local reduced model. This can be represented as the succeeding function:

For the choice of projection basis, we have the same advantages or disadvantage when using the two basic models, or a combination of the two basic models.

The methods apply to nonlinear systems by the mature linear system methods, TPWL is able to capture strongly nonlinear effects, with sufficiently accurate and meanwhile, it is cost efficient.

However, it has no posteriori error bounds, and the method does not guarantee the stable and passive properties. Furth more, it is not totally automatic. This drawback restrains its use.

2.3.3 Other SVD-Krylov methods

An algorithm using Laguerre functions is very suitable for circuit synthesis. The algorithm based on the decomposition of the system transfer matrix into orthogonal scaled Laguerre functions, defined as following:

where α is a positive scaling parameter and ln (t) is the Laguerre polynomial

By using the Laguerre functions, we can build the link with Padé approximation, the block Arnoldi process and the singular value decomposition (SVD), this permits a simple and stable implementation of the algorithm. In addition, the method is provably passive, but the method is computational cost.

3 Conclusions

Generally, the advantages of SVD methods are that they have a fully automatic algorithm and an error bound. However, they are computational cost and do not usually preserve the systems properties like passivity, these drawbacks limit the use of it to large order systems. Krylov-subspace methods have a common disadvantage in practical application: the difficulty to control the error. Error estimator does exist for some methods but they require expensive additional computation. Recent researches are concentrated to the union of the two kind conventional methods through technics like empirical gramians, rational Krylov or TPWL. However, empirical gramians methods are just applicable for control-affine systems and cant capture strong non-linearity. As to rational Krylov or TPWL, the main obstacles are that they are not fully computer automatically in sampling method. To providing some heuristic footpath, other data-driven models like the surrogate models[8] developing rapidly, they can be considered as an alternative to direct model reduction methods.

[References]

[1]A.C.Antoulas,D.C.Sorensen and S.Gugercin.A survey of model reduction methods for large-scale systems, Contemporary mathematics,2006.

[2]S.Gugercin,A.C.Antoulas,A survey of model reduction by balanced truncation and some new results,International Journal of Control,2004.

[3]Moris Lohmann and Behnam Salimbahrami,Introduction to Krylov Subspace Methods in Model Order Reduction,2003.

[4]Stefan Güttel,Rational Krylov approximation of matrix functions:Numerical methods and optimal pole selection, GAMM-Mitteilungen Volume 36,Issue 1,2013,pp.8-31.

[5]Christian Himpe,Mario Ohlberger,Empirical Gramian Framework,WWU Münster,2013.

[6]René Pinnau,Model reduction via proper orthogonal decomposition,2008,pp 95-109.

[7]K.Mohaghegh,M.Striebel,Nonlinear Model Order Reduction Based on Trajectory Pievewise Linear Approach:comparing different linear cores,2010,pp.563-570.

[8]S.Koziel,D.E.Ciaurri and L.Leifsson,Surrogate-based Methods,Computer Optimization,Methods and Algotithms,SCI 356, 2011,pp.33-59.