Balanced Truncation

2013-05-17T06:38:08Z

Kuerschner:

Balanced Truncation

2013-05-15T08:42:17Z

Kuerschner:

Balanced Truncation

2013-05-15T08:41:24Z

Kuerschner:

2013-04-25T09:11:14Z

Kuerschner:

[[Category:benchmark]]
[[Category:linear]]
[[Category:time invariant]]
[[Category:first differential order]]
[[Category:differential algebraic system]]
__NUMBEREDHEADINGS__

==Description==

These first order systems are given in generalized state space form

<math>
E\dot{x}(t)=A x(t)+B u(t), \quad
y(t)=Cx(t)+Du(t),\quad E,A\in\mathbb{R}^{n\times n},~B\in\mathbb{R}^{n\times m},~C\in\mathbb{R}^{p\times n},~D\in\mathbb{R}^{p\times m}
</math>

and originated at [http://www.cepel.br/ CEPEL] for simulating large power systems.

They come in different sizes and variants, including both SISO and MIMO systems having regular or singular <math>E</math> matrices. In the latter case the DAEs are of index 1 and using simple row and column permutations, <math>E,A</math> can be brought into the form

<math>
E=\left[ \begin{array}{cc}I_{n_f}&0\\0&0\end{array}\right],\quad A=\left[ \begin{array}{cc}A_{11}&A_{12}\\A_{21}&A_{22}\end{array}\right],
</math>

where <math>n_f</math> denotes the number of finite eigenvalues in <math>\Lambda(A,E)</math> and <math>A_{22}\in\mathbb{R}^{n-n_f\times n-n_f}</math> is regular.
A complete overview over these systems can be found in table below. The power system served as benchmark examples for [[Modal truncation|Dominant Pole based Modal Truncation]]<ref name="MarLP96"></ref><ref name="RomM06a"></ref><ref name="RomM06b"></ref><ref name="Rom07"></ref><ref name="Kue10"></ref> and for a special adaption<ref name="FreRM08"></ref> of [[Balanced Truncation]] for the DAE systems.

==Data==
The table below lists the charateristics of all power systems. The files can be downloadet at [https://sites.google.com/site/rommes/software https://sites.google.com/site/rommes/software].

{| class="wikitable sortable" style="text-align: center; width: auto;"
|-
! Name
! <math>n</math>
! <math>m</math>
! <math>p</math>
! Type
|-
|New England
|66
|1
|1
|ODE
|-
|BIPS/97
|13251
|1
|1
|DAE
|-
|BIPS/1997
|13250
|1
|1
|DAE
|-
|BIPS/2007
|21476
|1
|1
|DAE
|-
|BIPS/97,MIMO8
|13309
|8
|8
|DAE
|-
|BIPS/97,MIMO28
|13251
|28
|28
|DAE
|-
|BIPS/97,MIMO46
|13250
|46
|46
|DAE
|-
|Juba5723
|40337
|2
|1
|DAE
|-
|Bauru5727
|40366
|2
|2
|DAE
|-
|zeros_nopss
|13296
|46
|46
|DAE
|-
|xingo6u
|20738
|1
|6
|DAE
|-
|nopss
|11685
|1
|1
|DAE
|-
|bips98_606
|7135
|4
|4
|DAE
|-
|bips98_1142
|9735
|4
|4
|DAE
|-
|bips98_1450
|11305
|4
|4
|DAE
|-
|bips07_1693
|13275
|4
|4
|DAE
|-
|bips07_1998
|15066
|4
|4
|DAE
|-
|bips07_2476
|16861
|4
|4
|DAE
|-
|bips07_3078
|21128
|4
|4
|DAE
|-
|PI Sections 20-80
|
|
|
|ODE
|}

==References==
<references>
<ref name="MarLP96">N. Martins, L. Lima, and H. Pinto, "Computing dominant poles
of power system transfer functions", IEEE Transactions on
Power Systems, vol.11, no.1, pp.162-170, 1996</ref>

<ref name="RomM06a">J. Rommes and N. Martins, "Efficient computation of transfer
function dominant poles using subspace acceleration", IEEE Transactions on
Power Systems, vol.21, no.3, pp.1218-1226, 2006</ref>

<ref name="RomM06b">J. Rommes and N. Martins, "Efficient computation of multivariable
transfer function dominant poles using subspace acceleration", IEEE Transactions on
Power Systems, vol.21, no.4, pp.1471-1483, 2006</ref>

<ref name="Rom07">J. Rommes, "Methods for eigenvalue problems with applications
in model order reduction", Ph.D. dissertation, Universiteit
Utrecht, 2007.</ref>

<ref name="FreRM08">F. Freitas, J. Rommes, and N. Martins, "Gramian-based reduction method applied to large
sparse power system descriptor models." IEEE Transactions on Power Systems, vol. 23, no. 3, pp. 1258-1270, 2008.</ref>

<ref name="Kue10">P. Kürschner, "Two-sided eigenvalue methods for modal approximation”, Master’s thesis, Chemnitz University of Technology,
Department of Mathematics, Germany, 2010.</ref>
</ references>

==Contact==

'' [[User:Rommes]]'' '' [[User:kuerschner]]''

Power system examples

2013-04-25T08:52:11Z

Kuerschner: Created page with "Category:benchmark Category:linear Category:time invariant Category:first differential order Category:differential algebraic system __NUMBEREDHEADINGS__ =..."

Modal truncation

2013-04-25T08:19:30Z

Kuerschner:

[[Category:method]]
[[Category:DAE order unspecified]]
[[Category:linear]]
[[Category:time invariant]]
[[Category:first differential order]]
[[Category:second differential order]]
[[Category:linear algebra]]

==Description==
Model truncation<ref name="Dav66"></ref> is one of the oldest MOR methods for linear time invariant systems

<equation id="gensys" shownumber>
<math>
E\dot{x}(t)=A x(t)+B u(t), \quad
y(t)=Cx(t)+Du(t).\qquad (1)
</math>
</equation>

The main idea is to construct the [[Projection_based_MOR|projection matrices]] as <math>V=[x_1,\ldots,x_r], W=[y_1,\ldots,y_r]</math> where the <math>x_i, y_i</math> are right and left eigenvectors corresponding to
certain eigenvalues <math>\lambda_i\in\Lambda(A,E)</math>. The eigentriples <math>(\lambda_i,x_i,y_i)</math> satisfy.

<math>
Ax_i=\lambda_iEx_i,\quad A^Hy_i=\overline{\lambda_i}E^Hy_i,\quad i=1,\ldots,r.
</math>

They are different ways to select this typically small subset of eigenvalues. An often used criterion is to take the eigenvalue closest to the imaginary axis, i.e. the ones with the smallest real part, and their associated eigenvectors into account. Dominant pole based modal truncation selects <math>(\lambda_i,x_i,y_i)</math> with respect to their contribution in the transfer function and is described below.

One advantage of such eigenvalue based MOR methods is that they can be easily adapted to more general time invariant systems, for instance, systems in second order form

<math>
M\ddot{x}(t)+D\dot{x}(t)+K x(t)=B u(t), \quad
y(t)=C_px(t)+C_v\dot x(t)+Du(t)
</math>

which occur frequently in vibration analysis for mechanical systems. There, <math>M,D,K</math> being referred to as Mass, Damping, and Stiffness matrix are represent a finite element discretization of the mechanical system. In fact, a large variety of modal truncation type approaches originated in this application<ref name="KouB08"></ref>, e.g., Condensation (Guyan reduction)<ref name="Guy65"></ref> and Component Mode Synthesis (Craig-Bampton)<ref name="CraB68"></ref>.
Modal truncation methods can also be generalized to handle linear, time-invariant system with higher time derivatives and even with time-delays, e.g.

<math>
E\dot{x}(t)=A x(t)+Fx(t-\tau)+B u(t), \quad
y(t)=Cx(t)+Du(t),
</math>

where <math>\tau\geq0</math> is the time-delay.

Other advantages are that modal truncation can in principle applied to DAEs of arbitrary index and to unstable systems. They do, however, preserve stability since they do not change the eigenvalues of the original system.
They rely on eigenvalue algorithms to compute the required eigentriplets. There are several algorithms available for this purpose for large and sparse matrices.

Disadvantages are the lack of a computationally feasible error bound and the often observed lower approximation accuracy compared to other MOR methods.

== Dominant pole based modal truncation ==

<figure id="bode">
<subfigure>
[[File:Transferf.jpg|350px|border|right|<caption>3D Bode plot of transfer function.</caption>]]
</subfigure>
<subfigure>
[[File:Bode_newengland.jpg|350px|border|right|<caption>2D Bode plot of transfer function.</caption>]]
</subfigure>
</figure>

This modal truncation variant aims at the identification of eigentriplets <math>(\lambda_i,x_i,y_i)</math> which have a strong contribution to the input-output behavior of the dynamical. For this purpose, let all eigenvalues be semisimple and consider the residue expansion of the transfer function matrix (exemplary of (1))

<equation id="residue" shownumber>
<math>H(s)=C(sE-A)^{-1}B+D=\sum\limits_{j=1}^{n_f}\frac{(Cx_j)(y_j^HB)}{s-\lambda_j}+D+R_{\infty},\qquad(2)</math>
</equation>

where <math>n_f</math> is the number of finite eigenvalue of <math>(A,E)</math> and <math>R_{\infty}</math> is the residue corresponding to the infinite eigenvalues. For simplicity we assume <math>R_{\infty}=0</math>. The quantities <math>R_j:=(Cx_j)(y_j^HB)</math> in the numerator of the above series are the residues w.r.t. <math>\lambda_i</math>. Each finite eigenvalue <math>\lambda_i</math> is pole of <math>H(s)</math> and is called dominant pole if its scaled residue norm
<math>
\frac{\|R_j\|}{|\real{\lambda_j}|}
</math>
is larger than the ones of the other eigentriples which corresponds in some sense to the largest summand in the residue expansion of <math>H(s)</math>. Dominant poles can be observed in the Bode, or sigma plot. The figures on the right illustrate this phenomenon for the [[New_England]] test system.

The upper figure shows a three dimensional surface plot of <math>H(s)</math> in a region in the left half plane. The poles of <math>H(s)</math> (eigenvalues of
<math>(A,E)</math>) are marked as black dots in the <math>\real(s)-\Im(s)</math>-plane. Observe that the function values grow in the limit
towards infinity as <math>s</math> reaches an eigenvalue <math>\lambda\in\Lambda(A,E)</math>. However, the poles marked as
thick blue dots elevate the function values in a stronger way and are the one with the largest scaled residues, i.e., the dominant poles. The cutsection of this plot along the <math>\Im(s)</math> axis gives the Bode plot and is shown in the bottom figure where peaks occur near the imaginary parts of the dominant poles which are marked by the blue dots.

Dominant pole based model truncation then amounts to compute the, say <math>r\ll n_f</math>, most dominant poles (i.e., the dominant eigentriplets) and
take the associated right and left eigenvectors as columns of the truncation matrices <math>V, W</math>. Equivalently, the reduced order model is obtained by truncating the residue expansion (2):

<math>H(s)\approx\tilde{H}(s)=\sum\limits_{j=1}^{r}\frac{(Cx_j)(y_j^HB)}{s-\lambda_j}+D</math>.

Note that <math>\tilde{H}(s)</math> constructed in that way is often called modal equivalent of <math>H(s)</math>.
A specially tailored eigenvalue algorithm to compute the sought dominant eigentriplets for this task is the (Subspace Accelerated) Dominant Pole Algorithm
<ref name="MarLP96"></ref><ref name="RomM06a"></ref><ref name="RomM06b"></ref><ref name="Rom07"></ref><ref name="Kue10"></ref>
.

A MATLAB implementation of this algorithms and certain variants of thereof can be found at [https://sites.google.com/site/rommes/software https://sites.google.com/site/rommes/software].

==References==
<references>
<ref name="Dav66">E. J. Davison, "A method for simplifying linear dynamic systems"
, IEEE Transaction on Automated Control, vol. 11, no. 1, 93–101, 1966</ref>

<ref name="KouB08">P. Koutsovasilis and M. Beitelschmidt, "Comparison of Model Reduction Techniques for Large Mechanical Systems", Multibody
System Dynamics, vol.20, no.2, pp.111-128, 2008</ref>

<ref name="Guy65">R.J. Guyan, "Reduction of Stiffness and Mass Matrices", AIAA Journal, vol.3, no.2, pp.380, 1965</ref>

<ref name="CraB68">R. Craig and M. Bampton, "Coupling of Substructures for Dynamic Analyses", AIAA Journal, vol.6, no.7, pp.1313-1319, 1968</ref>

<ref name="MarLP96">N. Martins, L. Lima, and H. Pinto, "Computing dominant poles
of power system transfer functions", IEEE Transactions on
Power Systems, vol.11, no.1, pp.162-170, 1996</ref>

<ref name="RomM06a">J. Rommes and N. Martins, "Efficient computation of transfer
function dominant poles using subspace acceleration", IEEE Transactions on
Power Systems, vol.21, no.3, pp.1218-1226, 2006</ref>

<ref name="RomM06b">J. Rommes and N. Martins, "Efficient computation of multivariable
transfer function dominant poles using subspace acceleration", IEEE Transactions on
Power Systems, vol.21, no.4, pp.1471-1483, 2006</ref>

<ref name="Rom07">J. Rommes, "Methods for eigenvalue problems with applications
in model order reduction", Ph.D. dissertation, Universiteit
Utrecht, 2007.</ref>

<ref name="Kue10">P. Kürschner, "Two-sided eigenvalue methods for modal approximation”, Master’s thesis, Chemnitz University of Technology,
Department of Mathematics, Germany, 2010.</ref>
</ references>

Modal truncation

2013-04-25T08:18:17Z

Kuerschner:

[[Category:method]]
[[Category:DAE order unspecified]]
[[Category:linear]]
[[Category:time invariant]]
[[Category:first differential order]]
[[Category:second differential order]]
[[Category:linear algebra]]

==Description==
Model truncation<ref name="Dav66"></ref> is one of the oldest MOR methods for linear time invariant systems

<equation id="gensys" shownumber>
<math>
E\dot{x}(t)=A x(t)+B u(t), \quad
y(t)=Cx(t)+Du(t).\qquad (1)
</math>
</equation>

The main idea is to construct the [[Projection_based_MOR|projection matrices]] as <math>V=[x_1,\ldots,x_r], W=[y_1,\ldots,y_r]</math> where the <math>x_i, y_i</math> are right and left eigenvectors corresponding to
certain eigenvalues <math>\lambda_i\in\Lambda(A,E)</math>. The eigentriples <math>(\lambda_i,x_i,y_i)</math> satisfy.

<math>
Ax_i=\lambda_iEx_i,\quad A^Hy_i=\overline{\lambda_i}E^Hy_i,\quad i=1,\ldots,r.
</math>

They are different ways to select this typically small subset of eigenvalues. An often used criterion is to take the eigenvalue closest to the imaginary axis, i.e. the ones with the smallest real part, and their associated eigenvectors into account. Dominant pole based modal truncation selects <math>(\lambda_i,x_i,y_i)</math> with respect to their contribution in the transfer function and is described below.

One advantage of such eigenvalue based MOR methods is that they can be easily adapted to more general time invariant systems, for instance, systems in second order form

<math>
M\ddot{x}(t)+D\dot{x}(t)+K x(t)=B u(t), \quad
y(t)=C_px(t)+C_v\dot x(t)+Du(t)
</math>

which occur frequently in vibration analysis for mechanical systems. There, <math>M,D,K</math> being referred to as Mass, Damping, and Stiffness matrix are represent a finite element discretization of the mechanical system. In fact, a large variety of modal truncation type approaches originated in this application<ref name="KouB08"></ref>, e.g., Condensation (Guyan reduction)<ref name="Guy65"></ref> and Component Mode Synthesis (Craig-Bampton)<ref name="CraB68"></ref>.
Modal truncation methods can also be generalized to handle linear, time-invariant system with higher time derivatives and even with time-delays, e.g.

<math>
E\dot{x}(t)=A x(t)+Fx(t-\tau)+B u(t), \quad
y(t)=Cx(t)+Du(t),
</math>

where <math>\tau\geq0</math> is the time-delay.

Other advantages are that modal truncation can in principle applied to DAEs of arbitrary index and to unstable systems. They do, however, preserve stability since they do not change the eigenvalues of the original system.
They rely on eigenvalue algorithms to compute the required eigentriplets. There are several algorithms available for this purpose for large and sparse matrices.

Disadvantages are the lack of a computationally feasible error bound and the often observed lower approximation accuracy compared to other MOR methods.

== Dominant pole based modal truncation ==

<figure id="bode">
<subfigure>
[[File:Transferf.jpg|350px|border|right|<caption>3D Bode plot of transfer function.</caption>]]
</subfigure>
<subfigure>
[[File:Bode_newengland.jpg|350px|border|right|<caption>2D Bode plot of transfer function.</caption>]]
</subfigure>
</figure>

This modal truncation variant aims at the identification of eigentriplets <math>(\lambda_i,x_i,y_i)</math> which have a strong contribution to the input-output behavior of the dynamical. For this purpose, let all eigenvalues be semisimple and consider the residue expansion of the transfer function matrix (exemplary of (1))

<equation id="residue" shownumber>
<math>H(s)=C(sE-A)^{-1}B+D=\sum\limits_{j=1}^{n_f}\frac{(Cx_j)(y_j^HB)}{s-\lambda_j}+D+R_{\infty},\qquad(2)</math>
</equation>

where <math>n_f</math> is the number of finite eigenvalue of <math>(A,E)</math> and <math>R_{\infty}</math> is the residue corresponding to the infinite eigenvalues. For simplicity we assume <math>R_{\infty}=0</math>. The quantities <math>R_j:=(Cx_j)(y_j^HB)</math> in the numerator of the above series are the residues w.r.t. <math>\lambda_i</math>. Each finite eigenvalue <math>\lambda_i</math> is pole of <math>H(s)</math> and is called dominant pole if its scaled residue norm
<math>
\frac{\|R_j\|}{|\real{\lambda_j}|}
</math>
is larger than the ones of the other eigentriples which corresponds in some sense to the largest summand in the residue expansion of <math>H(s)</math>. Dominant poles can be observed in the Bode, or sigma plot. The figures on the right illustrate this phenomenon for the [[New_England]] test system.

The upper figure shows a three dimensional surface plot of <math>H(s)</math> in a region in the left half plane. The poles of <math>H(s)</math> (eigenvalues of
<math>(A,E)</math>) are marked as black dots in the <math>\real(s)-\Im(s)</math>-plane. Observe that the function values grow in the limit
towards infinity as <math>s</math> reaches an eigenvalue <math>(A,E)</math> of <math>(A,E)</math>. However, the poles marked as
thick blue dots elevate the function values in a stronger way and are the one with the largest scaled residues, i.e., the dominant poles. The cutsection of this plot along the <math>\Im(s)</math> axis gives the Bode plot and is shown in the bottom figure where peaks occur near the imaginary parts of the dominant poles which are marked by the blue dots.

Dominant pole based model truncation then amounts to compute the, say <math>r\ll n_f</math>, most dominant poles (i.e., the dominant eigentriplets) and
take the associated right and left eigenvectors as columns of the truncation matrices <math>V, W</math>. Equivalently, the reduced order model is obtained by truncating the residue expansion (2):

<math>H(s)\approx\tilde{H}(s)=\sum\limits_{j=1}^{r}\frac{(Cx_j)(y_j^HB)}{s-\lambda_j}+D</math>.

Note that <math>\tilde{H}(s)</math> constructed in that way is often called modal equivalent of <math>H(s)</math>.
A specially tailored eigenvalue algorithm to compute the sought dominant eigentriplets for this task is the (Subspace Accelerated) Dominant Pole Algorithm
<ref name="MarLP96"></ref><ref name="RomM06a"></ref><ref name="RomM06b"></ref><ref name="Rom07"></ref><ref name="Kue10"></ref>
.

A MATLAB implementation of this algorithms and certain variants of thereof can be found at [https://sites.google.com/site/rommes/software https://sites.google.com/site/rommes/software].

==References==
<references>
<ref name="Dav66">E. J. Davison, "A method for simplifying linear dynamic systems"
, IEEE Transaction on Automated Control, vol. 11, no. 1, 93–101, 1966</ref>

<ref name="KouB08">P. Koutsovasilis and M. Beitelschmidt, "Comparison of Model Reduction Techniques for Large Mechanical Systems", Multibody
System Dynamics, vol.20, no.2, pp.111-128, 2008</ref>

<ref name="Guy65">R.J. Guyan, "Reduction of Stiffness and Mass Matrices", AIAA Journal, vol.3, no.2, pp.380, 1965</ref>

<ref name="CraB68">R. Craig and M. Bampton, "Coupling of Substructures for Dynamic Analyses", AIAA Journal, vol.6, no.7, pp.1313-1319, 1968</ref>

<ref name="MarLP96">N. Martins, L. Lima, and H. Pinto, "Computing dominant poles
of power system transfer functions", IEEE Transactions on
Power Systems, vol.11, no.1, pp.162-170, 1996</ref>

<ref name="RomM06a">J. Rommes and N. Martins, "Efficient computation of transfer
function dominant poles using subspace acceleration", IEEE Transactions on
Power Systems, vol.21, no.3, pp.1218-1226, 2006</ref>

<ref name="RomM06b">J. Rommes and N. Martins, "Efficient computation of multivariable
transfer function dominant poles using subspace acceleration", IEEE Transactions on
Power Systems, vol.21, no.4, pp.1471-1483, 2006</ref>

<ref name="Rom07">J. Rommes, "Methods for eigenvalue problems with applications
in model order reduction", Ph.D. dissertation, Universiteit
Utrecht, 2007.</ref>

<ref name="Kue10">P. Kürschner, "Two-sided eigenvalue methods for modal approximation”, Master’s thesis, Chemnitz University of Technology,
Department of Mathematics, Germany, 2010.</ref>
</ references>