1 Introduction

Very large scale integration and computer-aided design techniques have enabled the communication switches to transmit data at higher rates. To achieve such higher data rates, several interconnect issues arise including ringing, reflections, distortion, cross talk. Interconnect network is modeled by thousands of RLC components, yielding a very large order system. Direct modeling, simulation and analysis of such interconnect network are very expensive in terms of computational cost. In order to address this issue, model order reduction (MOR) is employed. Useful MOR techniques provide ease in the analysis, design and simulation of large complex system by preserving the fundamental characteristics of the original system like stability and passivity. Moreover, these useful MOR techniques have low approximation error. For system with interconnects, passivity is of prime concern [12] and the reduced-order models (ROMs) should preserve the passivity property of original system so as to avoid artificial oscillations during transient simulations. Note that, a system is guaranteed to be stable if it is passive, however converse is not guaranteed.

Odabasiogoul et al. [15] introduced a method known as passive reduced-order interconnect macromodeling algorithm (PRIMA) which preserves the passivity of RLC systems [12]. Beside PRIMA, other passivity preserving MOR techniques include Phillip’s et al. [16], Unneland et al. [18], Yan et al. [21]. However, Phillip’s et al. [16] and Unneland et al. [18] techniques are applicable for unweighted systems only, whereas PRIMA and Yan et al. [21] techniques require special descriptor form. The proposed technique has the advantage to preserve passivity for two sided weighted scenario for a given frequency of interest. Moreover, it does not require special descriptor form and is applicable to standard state space systems.

Heydari and Pedram [5] introduced frequency weighted passivity preserving technique for strictly proper original systems. Various frequency weighted MOR techniques have been proposed in the literature [1,2,3,4,5,6,7,8]; however, these do not preserve passivity in ROMs. Some interesting frequency limited MOR results appear in [4,5,6,7].

In another work [13], existing frequency weighed MOR techniques [1, 11, 20] are modified to preserve passivity of ROMs obtained from the original passive systems. Recently, it is pointed out in [14] that the passivity preserving results presented in Heydari and Pedram [5] are incorrect and passivity is not preserved for double sided weighting case. The work in [5] neither retains passivity nor stability in the presence of double sided weighting case [14]. This is due to (as pointed out in [14]), simultaneously diagonalizing Gramians corresponding to different systems instead of one system being reduced. Following similar/same argument, the results in [13] also do not guarantee passivity in ROM. To the author’s knowledge, there is no scheme in literature, which guarantees to preserve passivity in ROMs for two sided frequency weighted MOR case.

In this work, a frequency weighted balanced truncation MOR technique is proposed which yields guaranteed passive ROMs for two sided weighting case also. The proposed technique provides a good approximation of the original system. Numerical examples are given to show the usefulness of proposed technique.

2 Main Results

The proposed technique is based on hierarchical balancing, wherein, a two sided passivity preserving frequency weighted balancing problem is considered as two one sided passivity preserving frequency weighted balancing problems in sequence, such that the balanced realization of the first one sided passivity preserving frequency weighted case is used for augmentation with the other side weighting. This work is motivated from [2], where stability preserving frequency weighted balanced MOR technique was proposed.

Consider the original passive system \(G(s) = C(sI-A)^{-1}B + D\), with the input weight \(V(s) = C_V(sI - A_V)^{-1}B_V + D_V\), and the output weight \(W(s) = C_W(sI - A_W)^{-1}B_W + D_W\), respectively, the input augmented system given by

$$\begin{aligned} G(s)V(s)= & {} {\bar{C}}_i (sI - {\bar{A}}_i)^{-1} {\bar{B}}_i + {\bar{D}}_i \end{aligned}$$
(1)

has the following minimal realizations

$$\begin{aligned} {\bar{A}}_i= & {} \left[ \begin{array}{c@{\quad }c} A &{} BC_V \\ 0 &{} A_V \ \end{array} \right] ,~~ {\bar{B}}_i = \left[ \begin{array}{c} B D_V \\ B_V \end{array} \right] \\ {\bar{C}}_i= & {} \left[ \begin{array}{c@{\quad }c} C&DC_V \end{array} \right] ,~~ {\bar{D}}_i= D D_V \end{aligned}$$

and satisfies the following Lur’e controllability equations:

$$\begin{aligned} {\bar{A}}_i{\bar{P}}_i + {\bar{P}}_i{\bar{A}}_i^T= & {} -{\bar{K}}_{c}{\bar{K}}_{c}^T \end{aligned}$$
(2)
$$\begin{aligned} {\bar{P}}_i{\bar{C}}_i^T - {\bar{B}}_i= & {} -{\bar{K}}_{c}{\bar{J}}_{c}^T \end{aligned}$$
(3)
$$\begin{aligned} {\bar{J}}_{c}{\bar{J}}_{c}^T= & {} {\bar{D}}_i + {\bar{D}}_i^T \end{aligned}$$
(4)

where

$$\begin{aligned}&{\bar{P}}_i = \left[ \begin{array}{c@{\quad }c} P_{11} &{} P_{12} \\ P_{12}^T &{} P_V \end{array} \right] , {\bar{K}}_c = \left[ \begin{array}{c@{\quad }c} K_{c1} &{} K_{c2} \\ \end{array} \right] \end{aligned}$$

Remark 1

For \({\bar{D}}_i+{\bar{D}}_i^T > 0\), the solution of Eqs. (2)–(4) are obtained by solving the following algebraic Riccati equation

$$\begin{aligned} \hat{A}{\bar{P}}_i + {\bar{P}}_i\hat{A}^T +{\bar{P}}_iC_i^T({\bar{D}}_i+{\bar{D}}_{i}^T)^{-1}{\bar{C}}_i{\bar{P}}_i + {\bar{B}}_i({\bar{D}}_i+{\bar{D}}_{i}^T)^{-1}{\bar{B}}_i^T = 0 \end{aligned}$$
(5)

where \(\hat{A} = {\bar{A}}_i{\bar{B}}_i({\bar{D}}_i+{\bar{D}}_i^T)^{-1}{\bar{C}}_i\). The solution of above Riccati equation yields frequency weighted controllability Gramian matrix \({\bar{P}}_i\) for the augmented system.

Remark 2

For strictly proper system (i.e., \(D=0\), \({\bar{D}}_i = 0\)), Lur’e equations (2)–(4) reduce to

$$\begin{aligned} {\bar{A}}_i{\bar{P}}_i + {\bar{P}}_i{\bar{A}}_i^T= & {} -{\bar{K}}_{c}{\bar{K}}_{c}^T \end{aligned}$$
(6)
$$\begin{aligned} {\bar{P}}_i{\bar{C}}_i^T= & {} {\bar{B}}_i \end{aligned}$$
(7)

which are solved using the method given in [17].

The (1,1) block of Eqs. (2)–(4) yield the following:

$$\begin{aligned} AP_{11} + P_{11}{A}^T= & {} X \end{aligned}$$
(8)
$$\begin{aligned} P_{11}C^T - BD_i= & {} -{K}_{c1}{J}_{ci}^T \end{aligned}$$
(9)
$$\begin{aligned} J_{ci}J_{ci}^T= & {} {\bar{D}}_i+{\bar{D}}_i^T \end{aligned}$$
(10)

where

$$\begin{aligned} X = -BC_{V} P_{12}^T - P_{12} C_{V}^T B^T - {K}_{c1}^T{K}_{c1} \end{aligned}$$
(11)

Let \({Q}_o\) be the observability Gramian of the system obtained by solving the following equations:

$$\begin{aligned} A^T{Q}_o + {Q}_oA= & {} -{K}_{o}^T{K}_{o} \end{aligned}$$
(12)
$$\begin{aligned} {Q}_oB - C^T= & {} -{K}_{o}^T{J}_{o} \end{aligned}$$
(13)
$$\begin{aligned} {J}_{o}^T{J}_{o}= & {} {D} + {D}^T \end{aligned}$$
(14)

Simultaneously diagonalizing the Gramians, we get

$$\begin{aligned} T_b^{-T} {Q}_o T_b^{-1}= & {} T_b P_{11} T_b^T = \hbox {diag}\left( \sigma _i\right) \end{aligned}$$
(15)

where \( \sigma _i \ge \sigma _{i+1},~i= 1,2,\ldots ,n-1 \).

Transforming the original system using balancing transformation \(T_b\), the input weighted balanced realization can be formed as:

$$\begin{aligned} A_b= & {} T_b^{-1} A T_b , ~~~~ B_b= T_b^{-1} B \nonumber \\ C_b= & {} C T_b , ~~~~~~~~~ D_b= D \end{aligned}$$
(16)

Remark 3

For input weighted case only, the ROMs are obtained by partitioning and truncating the realization \(\{A_b, B_b, C_b, D_b\}\) upto the desired order.

Remark 4

The ROMs obtained using input/one side weighting case are passive. This follows from section II-B of [14].

Now, consider the hierarchical output passivity preserving frequency weighted portion. Let the output augmented system be given by:

$$\begin{aligned} W(s)G(s)= & {} {\bar{C}}_o (sI - {\bar{A}}_o)^{-1} {\bar{B}}_o + {\bar{D}}_o \end{aligned}$$
(17)

where

$$\begin{aligned} {\bar{A}}_o= & {} \left[ \begin{array}{c@{\quad }c} A_b &{} 0 \\ B_W C_b &{} A_W \ \end{array} \right] , ~~ {\bar{B}}_o = \left[ \begin{array}{c} B_b \\ B_WD_b \end{array} \right] \\ {\bar{C}}_o= & {} \left[ \begin{array}{c@{\quad }c} D_W C_b&C_W \end{array} \right] ,\quad {\bar{D}}_o=D_W D_b \end{aligned}$$

Note here, the system realization \(\left\{ A_b,B_b,C_b,D_b\right\} \) is used for finding the augmented system W(s)G(s). The frequency weighted observability Gramian \({\bar{Q}}_o\) satisfies the following Lur’e equations

$$\begin{aligned} {\bar{A}}_{o}^T{\bar{Q}}_o + {\bar{Q}}_o{\bar{A}}_{o}= & {} -{\bar{K}}_{o}^T{\bar{K}}_{o} \end{aligned}$$
(18)
$$\begin{aligned} {\bar{Q}}_o{\bar{B}}_o - {\bar{C}}_o^T= & {} -{\bar{K}}_{o}^T{\bar{J}}_{o} \end{aligned}$$
(19)
$$\begin{aligned} {\bar{J}}_{o}^T{\bar{J}}_{o}= & {} {\bar{D}}_o + {\bar{D}}_o^T \end{aligned}$$
(20)

where

$$\begin{aligned}&{\bar{Q}}_o = \left[ \begin{array}{c@{\quad }c} Q_{11} &{} Q_{12} \\ Q_{12}^T &{} Q_W \end{array} \right] , {\bar{K}}_o = \left[ \begin{array}{c} K_{o1} \\ K_{o2} \\ \end{array} \right] \end{aligned}$$

Remark 5

For higher order systems with \({\bar{D}}_o+{\bar{D}}_o^T > 0\), the solution of Eqs. (18)–(20) are obtained by solving the following algebraic Riccati equation

$$\begin{aligned} \hat{A}_o^T{\bar{Q}}_o + {\bar{Q}}_o\hat{A}_o +{\bar{Q}}_o{\bar{B}}_o({\bar{D}}_o + {\bar{D}}_o^T)^{-1}{\bar{B}}_o^T{\bar{Q}}_o+ {\bar{C}}_o^T({\bar{D}}_o + {\bar{D}}_o^T)^{-1}{\bar{C}}_o = 0 \end{aligned}$$
(21)

where \(\hat{A} = {\bar{A}}_o{\bar{B}}_o({\bar{D}}_o+{\bar{D}}_o^T)^{-1}{\bar{C}}_o\).

Remark 6

For strictly proper system (i.e., \(D=0\), \({\bar{D}}_o = 0\)), Lur’e equations (18)–(20) reduce to

$$\begin{aligned} {\bar{A}}_{o}^T{\bar{Q}}_o + {\bar{Q}}_o{\bar{A}}_{o}= & {} -{\bar{K}}_{o}^T{\bar{K}}_{o} \end{aligned}$$
(22)
$$\begin{aligned} {\bar{Q}}_o{\bar{B}}_o= & {} {\bar{C}}_{o}^{T} \end{aligned}$$
(23)

which are solved using the method given in [17].

Expanding the (1,1) block of Eqs. (18)–(20) yields

$$\begin{aligned} {A_b}^T Q_{11} + Q_{11}A_b= & {} Y \end{aligned}$$
(24)
$$\begin{aligned} Q_{11}B - C^TD_o^T= & {} -K_{o1}^TJ_{oo} \end{aligned}$$
(25)
$$\begin{aligned} J_{oo}^TJ_{oo}= & {} {\bar{D}}_o + {\bar{D}}_o^T \end{aligned}$$
(26)

where

$$\begin{aligned} Y= - C_b^T B_{W}^T Q_{12}^T - Q_{12} B_{W} C_b - {K}_{o1}^T{K}_{o1} \end{aligned}$$
(27)

Let \({P}_i\) be the controllability Gramian for the transformed system obtained by solving the following equations:

$$\begin{aligned} {A}_b{P}_i + {P}_i{A}_b^T= & {} {K}_{c}{K}_{c}^T \end{aligned}$$
(28)
$$\begin{aligned} {P}_i{C}_b^T - {B}_b= & {} -{K}_{c}{J}_{c}^T \end{aligned}$$
(29)
$$\begin{aligned} {J}_{c}{J}_{c}^T= & {} {D}_b + {D}_b^T \end{aligned}$$
(30)

Simultaneously diagonalizing the Gramians \(P_i\) and \(Q_{11}\), we get

$$\begin{aligned} T^{-T} Q_{11} T^{-1}= & {} T P_i T^T = \hbox {diag}\left( \sigma _i\right) \end{aligned}$$
(31)

\( \sigma _i \ge \sigma _{i+1},~i= 1,2,\ldots ,n-1 \) and \( \sigma _r > \sigma _{r+1} \). Applying the similarity transformation to the input weighted balanced realization, the two sided frequency weighted balanced realization is obtained as following:

$$\begin{aligned} \left[ \begin{array}{c|c} A_{\mathrm{bal}} &{} B_{\mathrm{bal}} \\ \hline C_{\mathrm{bal}} &{} D_{\mathrm{bal}} \end{array} \right]= & {} \left[ \begin{array}{c|c} T^{-1}A_bT &{} T^{-1}B_b \\ \hline C_bT &{} D_b \end{array} \right] \nonumber \\= & {} \left[ \begin{array}{c|c} T^{-1}T_b^{-1}AT_bT &{} T^{-1}T_b^{-1}B \\ \hline CT_bT &{} D \end{array} \right] \end{aligned}$$
(32)

The ROM can be obtained by partitioning and truncating up to the appropriate order.

Remark 7

The similarity transformation matrix \(T_b\) has been constructed using the positive semidefinite matrices \({Q}_o\) and \(P_{11}\). The matrix \(T_b\) is then used in the calculation of the final transformation matrix, which is constructed using positive definite matrices \(Q_{11}\) and \(P_i\). The proposed hierarchical technique ensures the diagonalization of Gramians matrices \(\{{Q}_o\), \(P_{11}\}\) and \(\{Q_{11}, P_i\)} to guarantee the passivity of ROMs [14].

Algorithm I Given the passive realizations, \(\{A,B,C,D\}\), \(\{A_V,B_V,C_V,D_V\}\), \(\{A_W,B_W,C_W,D_W\}\)

  1. 1.

    Find the augmented system realization \(\{A_i,B_i,C_i,D_i\}\) using equation (1).

  2. 2.

    Solve the Lur’e equations (8)–(10) and (12)-(14) for finding the controllability (\(P_{11}\)) and observability (\(Q_o\)) Gramians, respectively.

  3. 3.

    Compute the transformation \( T_b \) using equation (15).

  4. 4.

    Find the intermediate balanced realization using the transformation \(T_b\) using equation (16).

  5. 5.

    Find the augmented system realization

    \(\{{\bar{A}}_o,{\bar{B}}_o,{\bar{C}}_o,{\bar{D}}_o\}\) using equation (17).

  6. 6.

    Solve the Lur’e equations (24)–(26) and (28)-(30) finding the observability (\(Q_{11}\)) and controllability (\(P_i\)) Gramians, respectively.

  7. 7.

    Compute the transformation T using equation (31).

  8. 8.

    Compute the frequency weighted balanced realization using equation (32)

  9. 9.

    The reduced-order model \(\{A_{11},B_1,C_1,D\}\) is obtained using

    $$\begin{aligned} \left[ \begin{array}{c|c} T^{-1}A_bT &{} T^{-1}B_b \\ \hline C_bT &{} D_b \end{array} \right]= & {} \left[ \begin{array}{cc|c} A_{11} &{} A_{12} &{} B_{1}\\ A_{21} &{} A_{22} &{} B_{2} \\ \hline C_{1} &{} C_{2} &{} D \end{array} \right] \end{aligned}$$

    where the dimension of \( A_{11}\) is equal to the dimension of \( \mathrm{diag}~\{ \sigma _1,\sigma _2, \ldots ,\sigma _r \} \).

Remark 8

The converse can also be defined, where output weighting is considered first in a sequence.

Fig. 1
figure 1

Nyquist plot of original and ROM

Full size image
Fig. 2
figure 2

Close-up view of Nyquist plot of original and ROM

Full size image
Fig. 3
figure 3

Eigenvalues plot of original and ROM

Full size image
Fig. 4
figure 4

Close-up view of eigenvalues plot of ROM

Full size image
Fig. 5
figure 5

Nyquist plot of original and ROM

Full size image
Fig. 6
figure 6

Eigenvalues plot of original and ROM

Full size image
Fig. 7
figure 7

Nyquist plot of original and ROM

Full size image
Fig. 8
figure 8

Eigenvalues plot of original and ROM

Full size image

3 Numerical Results

Example 1

Consider a sixth-order single lossy line modeled by ladder RLC circuit system [14] with parameter values as \(R_s = 1 {\varOmega }\), \(R_i = 1 {\varOmega }\), \(L_i = 0.01 H\), \(C_i = 1 F\). A system realization G(s) is given by:

$$\begin{aligned} A= & {} \left[ \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} 0 &{} 0 &{} 0 &{} 100 &{} -100 &{} 0\\ 0 &{} 0 &{} 0 &{} 0 &{} 100 &{} 0\\ 0 &{} 0 &{} -110 &{} 0 &{} 0 &{} -100\\ -100 &{} 0 &{} 0 &{} -10 &{} 0 &{} 100\\ 100 &{} -100 &{} 0 &{} 0 &{} -10 &{} 0\\ 0 &{} 0 &{} 100 &{} -100 &{} 0 &{} 0 \end{array} \right] \\ B= & {} \left[ \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} 0 &{} 0 &{} 100 &{} 0 &{} 0 &{} 0 \\ \end{array} \right] ^\mathrm{T}\\ C= & {} \left[ \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} 0 &{} 0 &{} 1 &{} 0 &{} 0 &{} 0 \\ \end{array} \right] \\ D= & {} 0 \end{aligned}$$

with input and output weighting functions

$$\begin{aligned} V(s) = W(s) = \frac{s+10}{s+2.1} \end{aligned}$$

Figure 1 shows the Nyquist plot for the original and third-order ROM obtained by the Heydari and Pedram [5] and proposed techniques. It can be seen that the Nyquist plot for the ROM lies in the left half plane for Heydari and Pedram, thus passivity of the ROM is not guaranteed in this case. While Nyquist plot for the ROM lies in the right half plane for the proposed technique, thus guaranteeing the passivity of the ROM. Figure 2 shows the close-up view of Fig. 1. Figure 3 shows the eigenvalues of the original system and the ROM obtained by the Heydari and Pedram [5] and proposed techniques. Figure 4 shows the close-up view of the eigenvalues plot of ROM for Heydari and Pedram [5] and proposed techniques. It can be observed that all the eigenvalues of the ROM for proposed technique are positive indicating that passivity is preserved in ROM. However, for Heydari and Pedram [5] technique, eigenvalues are negative indicating that passivity is not preserved in ROM in this case.

Example 2

Consider a fifth-order original passive system of RLC ladder network [10] with parameter values as \(R_s = 5 {\varOmega }\), \(R_i = 0.5 {\varOmega }\), \(L_i = 0.1 H\), \(C_i = 0.1 F\). A system realization G(s) is given by:

$$\begin{aligned} A= & {} \left[ \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} -20 &{} -10 &{} 0 &{} 0 &{} 0\\ 10 &{} 0 &{} -10 &{} 0 &{} 0\\ 0 &{} 10 &{} 0 &{} -10 &{} 0\\ 0 &{} 0 &{} 10 &{} 0 &{} -10\\ 0 &{} 0 &{} 0 &{} 10 &{} -2\\ \end{array} \right] \\ B= & {} \left[ \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} 20 &{} 0 &{} 0 &{} 0 &{} 0 \\ \end{array} \right] ^\mathrm{T}\\ C= & {} \left[ \begin{array}{c@{\quad }c@{\quad }c@{\quad }c@{\quad }c@{\quad }c} -2 &{} 0 &{} 0 &{} 0 &{} 0 \\ \end{array} \right] \\ D= & {} 2 \end{aligned}$$

with weighting functions

$$\begin{aligned} V(s) = W(s) = \frac{s+1}{s+3} \end{aligned}$$

Figure 5 shows the Nyquist plot for the original and third-order ROM obtained by the proposed technique. It can be seen that the Nyquist plot for the ROM lies in the right half plane, thus guaranteeing the passivity of the ROM. Figure 6 shows the eigenvalues of the original system and the ROM. It can be observed that all the eigenvalues of the ROM are positive indicating that passivity is preserved in ROM.

Example 3

Consider a 1000th order original passive system of a transmission line modeled by a 500 ladder RLC section [13] with parameter values as \(R_L = 0.1 {\varOmega }\), \(R_C = 1 {\varOmega }\), \(L_i = 0.1 H\), \(C_i = 0.1 F\) with weighting functions

$$\begin{aligned} V(s)= W(s) = \frac{s+0.01}{s+0.05} \end{aligned}$$

Figure 7 shows the Nyquist plot for the original and second-order ROM obtained by the proposed technique. It can be seen that the Nyquist plot for the ROM lies in the right half plane, thus guaranteeing the passivity of the ROM. Figure 8 shows the eigenvalues of the original system and the ROM. It can be observed that all the eigenvalues of the ROM are positive indicating that passivity is preserved in ROM.

4 Conclusion

In this work, a passivity preserving frequency weighted balanced MOR technique is presented. Balancing is performed in hierarchical manner. Simulation results show that the ROMs obtained by the proposed technique are passive.