Ordnungsreduktion linearer und nichtlinearer Systeme Order ......Ordnungsreduktion linearer und nichtlinearer Systeme Order Reduction of Linear and Nonlinear Systems Boris Lohmann,

Ordnungsreduktion linearer und nichtlinearer Systeme

Order Reduction of Linear and Nonlinear Systems

Boris Lohmann, TU München

with R. Eid, H. Panzer, R. Castañé, T. Wolf

Elgersburg Workshop, 3. März 2010

2Lohmann: Ordnungsreduktion, 03.03.2010

Motivation

techn. System

ODEs PDEs

Modellbildung

Diskretisierung

Reduz. Modell (ODEs)

Ordnungsreduktion


Teil 1:Ordnungsreduktion linearer Modelle


u

b

b

bu

n

q

n

q

⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢

⎣

⎡

+

⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢

⎣

⎡

=

=+= −−

M

M

O

O

&

11

11

z

bVAVzVz

λ

λ

λ

Lineare Modellreduktion durch Projektion

Originalmodell: ,

Beispiel: Modale Reduktion:

ubAxx +=& xcTy =

[ ]zVzc nqT cccy LL1==


Modale Darstellung

Pfad entfernen, falls klein ist

ii cb ⋅


u

b

b

bu

n

q

n

q

⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢

⎣

⎡

+

⎥⎥⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢⎢⎢

⎣

⎡

=

=+= −−

M

M

O

O

&

11

11

z

bVAVzVz

λ

λ

λ

Modellreduktion durch Projektion

Originalmodell: ,

Beispiel: Modale Reduktion:

ubAxx +=& xcTy =

[ ]zVzc nqT cccy LL1==

urr

obenrlinksobenr 32143421&

bA

bVxAVVx 11 −− +=

rlinksT

Tr

y xVcc321

=

Reduziertes Modell

Weitere Beispiele: Balancieren und Abschneiden, Krylov-Unterraumverfahren

A VTW

Projektion


Verfahren des “Balancieren und Abschneiden”

Input outputSystem (states)

I/O response

I/S response S/O response

Balancieren: Zustandstransformieren derart, dass(energieorientierte) Steuer- und Beobachtbarkeitsmaße, die Gramschen, sich gleichen.

Abschneiden: Zustandsvariablen mit geringemenergetischem Anteil am Ein-Ausgangsverhalten werdenentfernt (=abgeschnitten). Durchführung mit Projektion. (Aktuelle Arbeiten: P. Benner)


Reduktion mittels Krylov-Unterraummethoden

Originalmodell: ubxxE +=& xcTy =

Projektionsmatrix V = beliebige Basis des sog. Krylov-Unterraums

{ }bEbEEbbbE 12 ,...,,,),( −= qq spanK

Projektionsmatrix W = beliebige Basis des Krylov-Unterraums

{ }cEcEccE 1)(,...,,),( −= qTTTq spanK

Reduziertes Modell: uTr

Tr

T bWVxWxEVW +=& rTy Vxc=


Übereinstimmende Momente

bIEc 1)()( −−= ssg T

Taylorreihe um s=0

...... iiTTT ss bEcEbcbc −−−−= {10 mmm i

321321

Momente

Übertragungsfunktion des Originalmodells:

Es werden 2q Momente zur Übereinstimmung gebracht.

Beweis für :0m

...

)(

)(

00

1

10

deqm

m

TT

TTT

TTTr

===

==

==−

−

bcVrc

VrWVWVc

bWVWVc

0


Vergleich

Sehr große lineare Modelle bis 1.000.000, (auch parametrischeModelle und in Sequenz mit B&A)

Systeme bis Ordnung 1000, Näherungen werden derzeit vorangetrieben bis 100.000

Mechanik, bis Ordnung 10.000

Anwendung

Numerisch sehr ro-bust, Interpretier-barkeit der Momen-te.Keine Stabilitäts-garantie (außer Sonderfälle)

Stabilitätserhaltend,Hohe Approxi-mationsgüte. Fehlerschranke existiert.

Stabilitätserhal-tend, transparent.

Güte unklar

Eigenschaften

Krylov-Unterraum-verfahren

Balancieren und Abschneiden

Modale ReduktionVerfahren


Ein neuer Zugang zur parametrischen Reduktion linearerModelle

A New Approach to the Parametric Reduction of linear models


Existing Methods

Multivariate moment matching approach (Weile et al. 99, Daniel et al. 04)+ Moment matching about the Laplace variable s and the parameter p.

- Affine parameter dependency is required

- Curse of dimensionality (reduced order grows rapidly even for small numbers of parameters)

Common projection approach (Leung et al. 05, Li et al. 05, Peng et al. 05)+ Common projection matrix calculated from several local models

+ Moment matching property for each of the local models

- Reduced order depends on the number of local models considered

- Affine parameter dependency is required to obtain a parametric reduced model

TBR-Interpolation-based approach (Baur et al. 08, 09)+ Interpolation between TFs of locally reduced systems obtained by TBR

+ Benefits from error bounds and stability of TBRs.

- Reduced order depends on the number of the local models considered

- Lightly damped modes can cause problems

Can a new approach avoid some of the disadvantages?


Starting PointSystem:

xcbxAx )(,)()( pyupp T=+=&Matrices A,b,c only available at discrete values p1,p2,… of p:

A(p1)=A1 , A(p2)=A2 ,…b(p1)=b1 , b(p2)=b2 ,…c(p1)=c1 , c(p2)=c2 ,…

?

p p1 p2

Interpolation

System 2

System 1

p3

System 3


Interpolation of system matrices

)(1 pω )(2 pω

Linear Interpolation of coefficients (system matrices):

xcybxAx ⎟⎠⎞

⎜⎝⎛=⎟

⎠⎞

⎜⎝⎛+⎟

⎠⎞

⎜⎝⎛= ∑∑∑

===

s

i

Tii

s

iii

s

iii pupp

111)(,)()( ωωω&

1)(!=∑ piω

= exact description if p affine: A=A0+A1p, b=b0+b1p, c=c0+c1p



Linear Interpolation of coefficients (system matrices):

xcybxAx ⎟⎠⎞

⎜⎝⎛=⎟

⎠⎞

⎜⎝⎛+⎟

⎠⎞

⎜⎝⎛= ∑∑∑

===

s

i

Tii

s

iii

s

iii pupp

111)(,)()( ωωω&

1)(!=∑ piω

1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6-0.4

-0.2

0

0.2

0.4

0.6

0.8

1


1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6-0.4

-0.2

0

0.2

0.4

0.6

0.8

1


Nonlin. Interpolation of coefficients (system matrices):

xcybxAx ⎟⎠⎞

⎜⎝⎛=⎟

⎠⎞

⎜⎝⎛+⎟

⎠⎞

⎜⎝⎛= ∑∑∑

===

s

i

Tii

s

iii

s

iii pupp

111)(,)()( ωωω&

1)(!=∑ piω


Traditional Reduction

Traditionally: apply one common projector pair V,W:

xcybxAx ⎟⎠⎞

⎜⎝⎛=⎟

⎠⎞

⎜⎝⎛+⎟

⎠⎞

⎜⎝⎛= ∑∑∑

===

s

i

Tii

s

iii

s

iii pupp

111)(,)()( ωωω&

VWT VWT V

WT

Problem: V (and W) need many columns to well approxi-mate all s local models! large reduced order.

(For instance, to match 2q moments of each of the s local models, the reduced model’s order will be sq , instead of q in non-parametric reduction)

VWT A = A’


New: Reduction by Local ProjectorsApply separate projectors Vi, Wi to all local models:

r

s

ii

Tii

s

ii

Tiir

s

iii

Tiir

s

iii

Tii u

xVcy

bWxVAWxVEW

⎟⎠

⎞⎜⎝

⎛=

⎟⎠

⎞⎜⎝

⎛+⎟

⎠

⎞⎜⎝

⎛=⎟

⎠

⎞⎜⎝

⎛

∑

∑∑∑

=

===

1

111

,

ω

ωωω &

+ Almost no additional numerical effort,+ Much smaller reduced models (factor s when matching

same number of moments).Question: are we allowed to sum up physically different

reduced vectors x ? Answer:

Not at once, but after giving the local reduced models a common physical interpretation of state variables(by applying transformations Ti, Mi)


(1) Choice of Ti: Define a linear combination of q “important” state variables and transform all local reduced models, to represent these state variables:

Interpolation of Transformed models (1)

321ix

rediiT

i

ˆ

,* xVRx =

{ xRx),(

*

nq

T=

{ rediiii

T

,* xTx

VR

=⇒

r

s

iii

Tii

s

ii

Tiiir

s

iiii

Tiiir

s

iiii

Tiii u

xTVcy

bWMxTVAWMxTVEWM

⎟⎠

⎞⎜⎝

⎛=

⎟⎠

⎞⎜⎝

⎛+⎟

⎠

⎞⎜⎝

⎛=⎟

⎠

⎞⎜⎝

⎛

∑

∑∑∑

=

−

==

−

=

−

1

1

11

1

1

1 ,

ω

ωωω &

(2) (1)

with [ ]sqnsvd VVR ...1×=[H. Panzer et. al 2010]

for instance


(2) Choice of Mi:

Interpolation of Transformed models (2)

1)( −= RWM Tii

r

s

iii

Tii

s

ii

Tiiir

s

iiii

Tiiir

s

iiii

Tiii u

xTVcy

bWMxTVAWMxTVEWM

⎟⎠

⎞⎜⎝

⎛=

⎟⎠

⎞⎜⎝

⎛+⎟

⎠

⎞⎜⎝

⎛=⎟

⎠

⎞⎜⎝

⎛

∑

∑∑∑

=

−

==

−

=

−

1

1

11

1

1

1 ,

ω

ωωω &

(2) (1)

because then ...)()(

1

11 =⎟⎠

⎞⎜⎝

⎛∑=

−−r

s

ii

Tii

Ti

Tii xVRVEWRW &ω

RRT RRT44 344 21

Projector onto R44 344 21

Projector onto Vi

[H. Panzer et. al 2010]


Types of Weighting Functions / Interpolations

Explicit weights Implicit interpolation

Linear interpolation

Nonlinearinterpolation

Matrices of the local reduced-order models

Splineinterpolation

Hermiteinterpolation

RBF interpolation


The Beam Model

Parameter: Length LThickness and width: 10 mmYoung Modulus: 2.105 Pa.Damping: Proportional/Rayleigh

Order of the original system: 720Order of the reduced system: 54 local models; Weights: Lagrange Int. s0: ICOP (Eid2009);

Force


The solar panel model

Order of the original system: 5892

Order of the reduced system: 602 local models; Weights: linear Interpolation

Parameter: Thickness t of the panel(varies between 0.25 and 0.5 mm)


(Asymptotic stability)

(Stability)

For stable system, there exist infinite W.

Outlook I: Stability using matrix measure m

Stability can be defined by the existence of a change of basissuch that:

Stability:

Pole-placement region :

Error bounds:

Parametric MOR:

Finding this W has clear advantages:

Implies stability and it is preserved for any one-sided projection.

We can compute the region in the complex plane wherethe eigenvalues of the reduced system will be.

Upper bounds for the norm of the error system can be computed.

For certain classes of systems finding a W is trivial ! [Castané 2009]

This approach offers also advantages for stability preserving pMOR.

Several algorithms! (Matrix balancing,Approx. Lyapunov, etc.)


Port Hamiltonian Systems are stable, and passive with output

A new structure preserving reduction scheme:

ugQxRJx +−= )(&

The reduced model ,

with

and with V being a basis of the Krylov subspace

matches q moments around s=s0 (Loh. et al 2009, Wolf et al 2009).

QgVgQVVQ

QRQVVRQJQVVJ

Tr

Tr

Tr

Tr

=

=

=

=

−1)(

( ) ( ){ }gIQRJgIQRJ qq ssspanK −− −−−−= 010 )(,...,)(

Outlook II: MOR of PCHD Models

QxgTy =

urrrr gxQRJx +−= )(&xQg r

Try =


References1. Lohmann, B. and Eid, R.: Efficient Order Reduction of Parametric and Nonlinear Models by Superposition of Locally Reduced

Models. In Lohmann, B. und Roppenecker, G. (Hrsg.): Methoden und Anwendungen der Regelungstechnik. Shaker Verlag, Aachen, 2009.

2. Lohmann, B. and Eid, R.: Challenges in Model Order Reduction. In Oberwolfach Reports and presented at the Oberwolfach Conference "Control Theory: On the Way to New Application Areas", 22.-27.02.2009.

3. Panzer, H., Mohring, J., Eid, R., Lohmann, B.: Parametric Model Order Reduction by Matrix Interpolation. Submitted to Automatisierungstechnik, at, February 2010.

4. Rewienski and J. White, A Trajectory Piecewise-linear Approach to Model Order Reduction and Fast Simulation of Nonlinear Circuits and Micromachined Devices, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22, (2003), 155–170.

5. U. Baur, P. Benner: Modellreduktion für parametrisierte Systeme durch balanciertes Abschneiden und Interpolation. Automatisierungstechnik (at) 08/2009, S.411-419.

6. A. C. Antoulas, Approximation of Large-Scale Dynamical Systems, SIAM, 2005.7. R. W. Freund, Model reduction methods based on Krylov subspaces. Acta Numerica, 12, (2003), 267–319.8. L. Daniel, C. S. Ong, S. C. Low, K. H. Lee, and J. K. White. A multiparameter moment matching model reduction approach for

generating geometrically parameterized interconnect performance models. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 23(5), (2004), 678–693.

9. K. Wulf: Quadratic and Non-Quadratic Stability Criteria for Switched Linear Systems, Ph.D Thesis, Hamilton Institute, NUI Maynooth, Ireland, 2005.

10. Eid, R.: Time Domain Model Reduction by Moment Matching. Dissertation, TU München 2009.11. Lohmann, B., Wolf, T., Eid, R. and Kotyczka, P.: Passivity Preserving Order Reduction of Linear Port-Hamiltonian Systems by

Moment Matching. Tech. Report TRAC-4/2009, No. 1, www.rt.mw.tum.de12. Wolf, T., Lohmann, B., Eid, R. and Kotyczka, P.: Passivity and Structure Preserving Order Reduction of Linear Port-Hamiltonian

Systems using Krylov subspaces. In print at European Journal of Control 2010. 13. Castañé, R., Eid, R., Lohmann, B.: Stability Preservation in Krylov-based Model Order Reduction. Workshop des GMA-

Fachausschusses 1.30, Salzburg 2009. 14. L. Peng, F. Liu, L. T. Pileggi, and S. R. Nassif. Modeling interconnect variabilityusing e±cient parametric model order reduction.

In Proc. of the Design, Automationand Test In Europe Conference and Exhibition, Munich, Germany, 958-963 2005.15. A. T. Leung and R. Khazaka. Parametric model order reduction technique for design optimization. Proc. Intl. Symp. Circuits

Syst., pages 1290-1293, 2005.16. X. Li, L. Peng, and L. T. Pileggi. Parameterized interconnect order reduction with explicit-and-implicit multi-parameter moment

matching for inter/intra-die variations. In International Conference on Computer Aided Design, San Jose, USA, 806-812, 2005.17. D. S. Weile, E. Michielssen, E. Grimme, and K. Gallivan. A method for generating rational interpolant reduced order models of

two-parameters linear systems. Appl. math. Letters, 12:93-102, 1999.


Teil 2:Ordnungsreduktion nichtlinearer Modelle


Nichtlineare Reduktion: Modelle

CxyuxFgBuAx

uxfx

=++=

=),(

),(&u(t) y(t)

Hohe Ordnung n

)(tx

Reduktion

u(t)

Niedrige Ordnung q < n

)(txr

)(ˆ tx

)(ˆ ty

R

RRRRR

WxxxCy

uxgFuBxAx

==

++=

ˆˆˆ

),ˆ(&


“Proper Orthogonal Decomposition”System:

1. Take Snapshots of State Trajectory:

2. Perform SVD of X , for low-rank approx.:

Dominant subspace and Approximation of x

3. Reduced Model:

),( uxfx =&

[ ])()()( 21),( NNn ttt xxxX L=

),(),(),(),(),(),(),(),(),( Nnnq

Tq

qnq

Nq

Tq

qqq

qnqNn

T

nnnnXUUVUVUX =Σ≈Σ=

xUx Tqdom = domq xUx =ˆ

),( uxUfUx rqTqr =&

tt1 t2 t3 t4 …

x1


Trajectory Piecewise Linear (TPWL) - 1

Idea: Representation of the original nonlinear model as a sum of piecewise-linear systems and then reducing each of the systems with a Krylov projection.

Original nonlinear model: Order N

Weighted Sum of slinearized models:

Order N

Weighted sum of s reduced linearized models:

Order q

Linearization around soperating points

Projection

State-dependent weights with unity sum

Jacobian of


TPWL - 2X2

X0 X1

X1

X2

X3

Version 1 (full sim.)1. Linearized model about x02. Simulation of the nonlin. sys. while

current state is close enough to lin. pt.3. Until end of trajectory, define a new lin. pt.

and linearize about it, then go to step 2. 4. Reduce the different resulting lin. sys.5. Choose the weightings according to the

current state

Given:

Version 2 (approx. trajectory)1. Linearized model about x02. Reduction using moment matching3. Approximation of the full state

vector4. Until end of trajectory, define a

new lin. pt. and go to step 2.5. Choose the weightings according

to the current state

• Training Input• Initial state• number of models to be

generatedX1’

X2’

X3’


Nonlinear parametric reduction by interpolation of locally reduced linear models

Given

Reduced system:

),( pxfx =&

Locally linear parametric representation (like in TPWL):

( )∑=

−+=s

iiiii p

1)(),( xxAfxx ω&

( )∑=

−+⋅=s

iiriii

Triir tptt

1))(()),(()( xxVAfWxVx ω&

ii pi

iii p

,|/),(

xxfAxff∂∂=

=

Outlook III

1=∑ ii ωω have to normalize


Reduktion durch Optimierung entlang Trajektorien

)1,(),()1,(

),(

nnqqdo xRx

uxFgBuAxx=

++=&

x& x

AF

Bu

),( uxg

rx&rx

rArF

rBu

),ˆ( uxg Wx̂

r

rrrrrr

WxxuWxgFuBxAx

=++=

ˆ),(&

Gesucht:

so dassxRxxx && ≈≈ randˆ

],,[, rrr FBAW⇓⇓

R

R

--+

e1e2-

+

dor xx ≈ , alsodox

Gegeben:


Diskussion

Alle drei Verfahren erfordern Simulationen des Originalmodells (außer erweitertes TPWL). Keine Stabilitätsgarantie, keine Fehlerschranken.

Proper Orthogonal Decomposition:☺ Reduziertes Modell durch SVD der Snapshotmatrix.

Mäßige Appriximationsgüte/Modellordnung.Trajectory Piecewise Linear:☺ Reduziertes Modell gültig in größeren Bereichen des Zustandsraums.

Kompliziertes reduziertes Modell, viele Parameter im Reduktionsvorgang.

Optimierung entlang Trajektorien:☺ Reduziertes Modell kann über geschlossene Formeln berechnet werden

(quadratisch optimale Matrizen).☺ Transparentes zuverlässiges Vorgehen, physikalische Interpretierbarkeit.

Günstige Wahl dominanter Zustandsgrößen unklar; nur geeignet für Systeme mit wenigen Nichtlinearitäten.

Reduzierte Modelle intern stark verkoppelt (Matrizen enthalten kaum Nullelemente). Lösung: durch Strukturvereinfachung mittels Genetischer Algorithmen


Genetischer Algorithmus zur Strukturvereinfachung

Reduziertes Modell einfacher Strukturberechnen (optimale Wahl von AR, BR, FR, W, die Nebenbedingungen berücksichtigend)

Reduz. Modell

Wandeln in HiNebenbedingungen

Erzeugung einerneuen Population

Individuum (Binärwort)

Fitness des reduz. Modells

Alte PopulationGA

SMO


Active Hydropneumatic Vehicle Suspension


Originalmodell der Ordnung 10


Blockschaltbild


Reduziertes Modell ohne Strukturvereinfachung

Gute Approximationsgüte aber hohe innereVerkopplung/Komplexität


Reduziertes Modell mit Strukturvereinfachung

Durch zeilenweise Optimierung schrumpft der Suchraum auf 114.63x103 Elemente, was 18.1x10-23 mal kleiner ist, als derursprüngliche vollständige Suchraum. 86 Elemente (von 98) sind Null, also 84% Nullen!


Wichtigste Methodenzweige und Entwicklungspotenzial

Krylov

- für große lineareSysteme

- Moment-Matching um verschiedene Entwick-lungspunkte

- Arnoldi/Lanczos -Alg.

?

SVD

Lin. Systeme: Balancieren und Abschneiden

Nichtlin. Systeme: POD

Sonstige

Lin. Systeme: ModaleVerfahren, Frequenz-bereichsverfahren

Nichtlin. Systeme: (lineare) Näherungenentlang Trajektorien

?z.B. Parametrische Reduktion, Kopplung von Teilsystemen, Numerik, Performanz.


Vielen Dank!

Documents

Ordnungsreduktion linearer und nichtlinearer Systeme Order ......Ordnungsreduktion linearer und nichtlinearer Systeme Order Reduction of Linear and Nonlinear Systems Boris Lohmann,