Balancing-Related Model Reduction of Circuit Equations Using Topological Structure

Abstract

In recent years, model order reduction has been recognized to be a powerful tool in analysis and simulation of integrated circuits. We consider balancing-related model reduction methods for differential-algebraic equations arising in circuit simulation. We show how positive real and bounded real balanced truncation can be used for passivity-preserving model reduction of circuit equations. These methods are based on balancing the solutions of projected Lur’e or Riccati matrix equations and admit computable error bounds. We also discuss efficient algorithms for solving such matrix equations that exploit the topological structure of circuit equations. Numerical experiments demonstrate the performance of the presented model reduction methods.

1 Introduction

Modern integrated circuits have hundreds of millions of semiconductor devices whose feature size is nowadays reaching the nanometer range. These devices are placed on several layers and interconnected to each other by wires. Due to increased packing density and interconnect length, modelling of thermal and electromagnetic effects is highly required in order to verify that the heat conduction and internal electromagnetic field do not disturb signal propagation. Design of VLSI circuits with distributed elements is no longer possible without computer simulations that involve numerical solution of coupled systems of partial differential equations and differential-algebraic equations (DAEs). After spatial discretization, such systems have very large state space dimension that makes the analysis and simulations unacceptably time consuming and expensive. In this context, model order reduction is of great importance.

A general idea of model order reduction is to approximate the large-scale system by a much smaller model that captures the input–output behavior of the original system to a required accuracy and also preserves essential physical properties such as stability and passivity. Many different model reduction approaches have been developed in computational fluid dynamics, control design and electrical and mechanical engineering, see [2, 15, 70] for recent books on this topic. One of the most used model reduction techniques in circuit simulation is moment matching approximation based on Krylov subspace methods, e.g., [4, 30, 38]. Although these methods are efficient for very large sparse problems, the resulting reduced-order systems have only locally good approximation properties. Another drawback of the moment matching methods is that stability and passivity are not necessarily preserved in the reduced-order models, so that usually post-processing is needed to realize these properties. Recently, passivity-preserving model reduction methods based on Krylov subspaces have been developed for structured systems arising in circuit simulation [31, 33, 45, 56] and also for general systems [3, 28, 41, 72]. However, none of these methods provides computable global error bounds.

Balanced truncation is another model reduction approach commonly used in control design. In order to capture specific system properties, different balancing techniques have been developed in the last thirty years for standard state space systems [26, 39, 53, 55, 60, 77] and also for DAEs [7, 14, 59, 63, 74]. In particular, passivity-preserving balanced truncation has been considered in [9, 13, 60, 63–65, 83]. An important property of balancing-related model reduction methods is the existence of computable error bounds. Unfortunately, these methods have a reputation for being very expensive since they involve solving (projected) Lyapunov and/or Riccati matrix equations. However, recent developments on iterative methods for such equations [16, 49, 57, 71, 75] show that balanced truncation methods can also be applied to large-scale problems.

In this paper, we give a brief survey on model reduction of circuit equations using balanced truncation and its relatives. In Sect. 3.2, we present some basic foundations from graph theory and network analysis required in the following. In Sect. 3.3, the balanced truncation model reduction approach for DAEs is described. Passivity-preserving model reduction methods for circuit equations based on positive real and bounded real balanced truncation are also considered. In Sect. 3.4, we discuss numerical solution of projected Lyapunov and Riccati equations with large-scale matrix coefficients. Section 3.5 contains some results of numerical experiments demonstrating the efficiency of the balancing-related model reduction techniques.

Throughout the paper, ${{\mathbb{R}}^{n,m}}$ and ${{\mathbb{C}}^{n,m}}$ denote the spaces of n × m real and complex matrices, respectively. The open left and right half-planes are denoted by ${{\mathbb{C}}_-}$ and ${{\mathbb{C}}_+}$, respectively, and $i=\sqrt{-1}$. The matrices A ^T and A ^* denote, respectively, the transpose and the conjugate transpose of ${A\in{\mathbb{C}}^{n,m}}$, and $A^{-T}=(A^{-1})^T$. An identity matrix of order n is denoted by I _n or simply by I. We use $\hbox{rank}(A)$ and ker(A) for the rank and the kernel of A, respectively. A matrix ${A\in{\mathbb{C}}^{n,n}}$ is positive definite (semidefinite), if v ^* Av > 0 ($v^*Av\geq 0$) for all non-zero ${v\in{\mathbb{C}}^n}$. Note that positive (semi)definiteness of A does not require A to be Hermitian. For ${A,B\in{\mathbb{C}}^{n,n}}$, we write A > B ($A\geq B$) if A − B is positive definite (semidefinite).

2 Circuit Equations

In this section, we briefly describe the formulation of linear RLC circuits via DAEs and discuss their properties. For more details on graph theory and network analysis, we refer to [1, 22, 44, 79].

A general electrical circuit can be modelled as a directed graph ${\mathfrak{G}}=({\mathfrak{N},\mathfrak{B})}$ whose vertices ${\mathfrak{n}}_{k}\in{\mathfrak{N}}$ correspond to the nodes of the circuit and whose edges (branches) ${\mathfrak{b}}_{k_1,k_2}=\langle{\mathfrak{n}}_{k_1},{\mathfrak{n}}_{k_2} \rangle\in{\mathfrak{B}}$ correspond to the circuit elements like capacitors, inductors and resistors. For the ordered pair ${\mathfrak{b}}_{k_1,k_2}=\langle{\mathfrak{n}}_{k_1},{\mathfrak{n}}_{k_2}\rangle$, we say that ${\mathfrak{b}}_{k_1,k_2}$ leaves ${\mathfrak{n}}_{k_1}$ and enters ${\mathfrak{n}}_{k_2}$. An alternating sequence ${({\mathfrak{n}}_{k_1},{\mathfrak{b}}_{k_1},{\mathfrak{n}}_{k_2}, \ldots, {\mathfrak{n}}_{k_{s-1}},{\mathfrak{b}}_{k_{s-1}}, {\mathfrak{n}}_{k_s})}$ of vertices and edges in ${\mathfrak{G}}$ is called a path connecting ${\mathfrak{n}}_{k_1}$ and ${\mathfrak{n}}_{k_s}$ if ${\mathfrak{b}}_{k_j}=\langle{\mathfrak{n}}_{k_j},{\mathfrak{n}}_{k_{j+1}}\rangle$ and ${\mathfrak{n}}_{k_i}\neq {\mathfrak{n}}_{k_j}$ for $2\leq i<j\leq s$. A path is closed if ${\mathfrak{n}}_{k_1}$ and ${\mathfrak{n}}_{k_s}$ are the same, and open if they are different. A closed path is called a loop. A graph ${\mathfrak{G}}$ is called connected if for every two vertices there exists an open path connecting them. A cutset is a set of edges of a connected graph whose removal disconnects the graph, and this set is minimal with this property. A subgraph of the graph ${\mathfrak{G}}$ is called a tree if it has all nodes of ${\mathfrak{G}}$, is connected and does not contain loops.

Any directed graph ${\mathfrak{G}}=({\mathfrak{N}},{\mathfrak{B})}$ with ${\mathfrak{N}}=\{{\mathfrak{n}}_1,\ldots,{\mathfrak{n}}_{n_\eta+1}\}$ and ${\mathfrak{B}}=\{{\mathfrak{b}}_1,\ldots,{\mathfrak{b}}_{n_b}\}$ can be described by an incidence matrix ${{\bf A}_0=[a_{kl}]\in{\mathbb{R}}^{n_\eta+1,n_b}}$ defined as

$$ a_{kl} = \left\{ \begin{array}{rl} 1 & \hbox{if edge }{\mathfrak{b}}_l \hbox{ leaves vertex }{\mathfrak{n}}_k,\\ -1 & \hbox{if edge }{\mathfrak{b}}_l \hbox{ enters vertex }{\mathfrak{n}}_k, \\ 0 & \hbox{otherwise}.\end{array}\right. $$

In a connected graph, any n _η rows of A ₀ are linearly independent. Thus, deleting any row from A ₀ yields a full rank matrix ${{\bf A}\in{\mathbb{R}}^{n_\eta,n_b}}$ known as reduced incidence matrix. For circuits, the deleted row corresponds to a reference (or grounding) node.

We now consider a general linear RLC circuit that contains linear resistors, inductors, capacitors, independent voltage sources and independent current sources only. Such circuits are often used to model the interconnects, transmission lines and pin packages in VLSI networks. They arise also in the linearization of nonlinear circuit equations around DC operating points. RLC circuits are completely described by the graph-theoretic relations like Kirchhoff’s current and voltage laws together with the branch constitutive relations that characterize the circuit elements. Kirchhoff’s current law states that the sum of the currents along all edges leaving and entering any circuit node is zero. Kirchhoff’s voltage law states that the sum of the voltages along the branches of any loop is zero. Let ${j=[j_{R}^T, j_{C}^T, j_{L}^T, j_{V}^T, j_{I}^T]^T\in{\mathbb{R}}^{n_b}}$ and ${v=[v_{R}^T, v_{C}^T, v_{L}^T, v_{V}^T, v_{I}^T]^T\in{\mathbb{R}}^{n_b}}$ denote the vectors of branch currents and branch voltages, respectively, and let the reduced incidence matrix ${\bf A}=[A_{R}, A_{C}, A_{L}, A_{V}, A_{I}]$ be partitioned accordingly, where the subscripts R, C, L, V and I stand for resistors, capacitors, inductors, voltage sources and current sources, respectively. Then Kirchhoff’s current and voltage laws can be expressed in the compact form as

$$ {\mathbf{A}}j=0, \quad{\mathbf{A}}^T \eta=v, $$

(3.1)

respectively, where ${\eta\in{\mathbb{R}}^{n_\eta}}$ denotes the vector of potentials of all nodes excepting the reference node.

The branch constitutive relations for the linear capacitors, inductors and resistors are given by

$${{\mathcal{C}}}\; {\frac{d}{dt}}\;v_{C}(t)=j_{C}(t), \quad v_{L}(t)= {{\mathcal{L}}} {\frac{d}{dt}}j_{L}(t), \quad v_{R}(t)={\mathcal R} j_{R}(t), $$

(3.2)

where ${{\mathcal{C}}\in{\mathbb{R}}^{n_C,n_C}}$, ${{\mathcal {L}}\in{\mathbb{R}}^{n_L,n_L}}$ and ${{\mathcal {R}}\in{\mathbb{R}}^{n_R,n_R}}$ are the capacitance, inductance and resistance matrices, respectively. These matrices are often diagonal and their diagonal entries are the capacitances, inductances and resistances of the capacitors, resistors and inductors, respectively. However, the diagonal structure gets lost in case of mutually coupled elements. If ${{\mathcal{R}}}$ and ${{\mathcal{L}}}$ are nonsingular, then ${{\mathcal {G}}={\mathcal{R}}^{-1}}$ and ${{\mathcal{S}}={\mathcal{L}}^{-1}}$ are the conductance and susceptance matrices, respectively.

Using relations (3.1) and (3.2), the behaviour of a linear RLC circuit can be described via modified nodal analysis (MNA) [79] by the following system of DAEs

$$ \begin{aligned} E\dot{x}(t) & = Ax(t)+Bu(t),\\ y(t) & = Cx(t)+Du(t), \end{aligned} $$

(3.3)

where

$$ \begin{aligned} E&=\left[\begin{array}{lll} A_{C}{{\mathcal{C}}} A_{C}^T &0 &0 \\ 0& {\mathcal L} &0 \\ 0&0&0\\ \end{array}\right], \quad A=\left[\begin{array}{lll} -A_{R}{{\mathcal G}} A_{R}^T &-A_{L} &-A_{V} \\ A_{L}^T& 0 & 0 \\ A_{V}^T& 0 &0\\ \end{array}\right],\\ C&=\left[\begin{array}{lll} -A_{I}^T &0 & 0\\ 0 &0 &-I\\ \end{array} \right] = B^T, \quad D=0, \end{aligned} $$

(3.4)

$$ x(t)= \left[\begin{array}{l}\eta(t)\\ j_{L}(t)\\ j_{V}(t)\\\end{array}\right], \quad u(t)=\left[\begin{array}{l} j_{I}(t)\\ v_{V}(t)\\ \end{array}\right] , \quad y(t)=-\left[\begin{array}{l}v_{I}(t)\\ j_{V}(t)\\\end{array}\right]. $$

The number of state variables $n=n_{\eta}+n_{L}+n_{V}$ is called the order of system (3.3), and $m=n_{I}+n_{V}$ is the number of inputs and outputs. In the following we will assume that the circuit is well-posed in the sense that it has neither V-loops nor I-cutsets. These assumptions can be written in terms of the incidence matrices as follows:

(A1)

The matrix A _V has full column rank, i.e., $\hbox{rank}(A_{V})=n_{V}$.

(A2)

The matrix $A_{CLRV} =\left[A_{C}, A_{L}, A_{R}, A_{V}\right]$ has full row rank, i.e., $\hbox{rank}(A_{CLRV})=n_\eta$.We will also assume that

(A3)

${{\mathcal{C}}},$${{\mathcal{G}}}$ and ${{\mathcal{L}}}$ are positive definite.

Assumptions (A1)–(A3) together guarantee that the matrix pencil λE − A is regular, i.e., det(λE − A) ≠ 0 for some ${\lambda\in{\mathbb{C}}}$, see [32]. In this case, we can define a transfer matrix G(s) = C(sE − A)⁻¹ B + D that describes the input–output relation of (3.3) in the frequency domain. The transfer function G is called proper if $\lim\nolimits_{s\to\infty} {\bf G}(s)<\infty$, and improper, otherwise. If $\lim\nolimits_{s\to\infty}{\bf G}(s)=0$, then G is called strictly proper.

Any regular pencil λE − A can be reduced into the Weierstrass canonical form

$$ E=T_l \left[\begin{array}{ll} I_{n_{f}} & 0 \\ 0 & E_\infty \\ \end{array}\right] T_r, \quad A = T_l \left[ \begin{array}{ll} A_f & 0 \\ 0 & I_{n_\infty} \\ \end{array}\right] T_r, $$

(3.5)

where T _l and T _r are the left and right nonsingular transformation matrices, and E _∞ is nilpotent with index of nilpotency μ, see [34]. The eigenvalues of A _f are the finite eigenvalues of λE − A, and E _∞ corresponds to an eigenvalue at infinity. The number μ is called the index of λE − A and also of the DAE system (3.3). Index concept plays an important role in the analysis and numerical solution of DAEs, e.g., [19, 20, 37, 46, 67]. The following proposition characterizes the index of the MNA equations (3.3), (3.4).

Proposition 1

[27] Let E and A be as in (3.4) and let (A1)–(A3) be fulfilled.

• 1. The index of the pencil λE − Ais at most two.

• 2. The index of λE − Ais equal to zero if and only if

  $$ n_V=0, \quad \hbox{rank}(A_C)=n_\eta. $$

  (3.6)

• 3. The index of λE − Ais equal to one if and only if

  $$ \hbox{rank}(Q_{C}^T A_{V})=n_{V}, \quad \hbox{rank}[A_{C}, A_{R}, A_{V} ]=n_{\eta}, $$

  (3.7)

  whereQ _C is a projector ontoker(A ^T _C ).

Considering the topological structure of the circuit, the conditions (3.6) imply that the circuit does not contain voltage sources and the circuit graph contains a capacitive tree. Furthermore, the first condition in (3.7) implies that the circuit does not contain CV-loops except for C-loops, whereas the second condition in (3.7) means that the circuit does not contain LI-cutsets.

Using the Weierstrass canonical form (3.5), the MNA system (3.3), (3.4) can be decoupled into the slow subsystem

$$ \dot{x}_1(t) = A_f x_1(t)+B_f u(t), $$

(3.8a)

$$ y_1(t)= C_f x_1(t), $$

(3.8b)

and the fast subsystem

$$ E_\infty \dot{x}_2(t) = x_2(t)+B_\infty u(t), $$

(3.9a)

$$ y_2(t)= C_\infty x_2(t), $$

(3.9b)

where $T_r x(t)=[ (x_1(t))^T, (x_2(t))^T ]^T, y(t)=y_1(t)+y_2(t)$ and

$$ T_l^{-1}B=\left[\begin{array}{l} B_f \\ B_\infty\\ \end{array}\right], \quad CT_r^{-1}=[C_f, C_\infty ]. $$

(3.10)

Equation (3.8a) with the initial condition $x_1(0)=x_1^0$ has a unique solution

$$ x_1(t)=e^{tA_{f}}x_1^0+\int\limits_{0}^{t}e^{(t-\tau)A_{f}}B_f u(\tau) d\tau $$

for any integrable input u and any initial vector ${x_1^0\in{\mathbb{R}}^{n_f}}$. Since the index μ of system (3.3), (3.4) does not exceed two, a unique solution of Eq. (3.9a) is given by

$$ x_2(t)=-B_\infty u(t)-E_\infty B_\infty \dot{u}(t). $$

This representation shows that for the existence of a continuously differentiable solution x of (3.3), (3.4), it is necessary that the input function u is μ times continuously differentiable. Moreover, the initial condition x(0) = x ₀ has to be consistent, i.e., $x_0=T_r^{-1}[(x_1^0)^T, (x_2^0)^T]^T$ must satisfy

$$ x_2^0=-B_\infty u(0)-E_\infty B_\infty \dot{u}(0). $$

If the initial vector x ₀ is inconsistent or the input u is not sufficiently smooth, then the solution of the MNA system (3.3), (3.4) may have impulsive modes [20].

2.1 Stability

Stability is a qualitative property of dynamical systems which describes the behaviour of their solutions under small perturbations in the initial data. For the linear time-invariant DAE system (3.3), stability can be characterized in terms of the finite eigenvalues of the pencil λE − A, e.g., [24]. System (3.3) is stable if all the finite eigenvalues of λE − A lie in the closed left half-plane and the eigenvalues on the imaginary axis are semi-simple, i.e., they have the same algebraic and geometric multiplicity. System (3.3) is asymptotically stable if the pencil λE − A is c-stable, i.e., all its finite eigenvalues lie in the open left half-plane. The following proposition gives the topological conditions for the asymptotic stability of the MNA equations (3.3), (3.4).

Proposition 2

[66] Let the matrices E and A be as in (3.4) and let (A1)–(A3) be fulfilled. Assume that ${{\mathcal{C}}}$ and ${{\mathcal{L}}}$ are symmetric and one of the following two pairs of topological conditions holds:

• 1.
  $$ \hbox{rank} [ A_{L},\; A_{V} ] = n_{L}+n_{V},\quad \hbox{rank} [ A_{R}, A_{V} ] = n_{\eta}, $$

  (3.11)
• 2.
  $$ \hbox{rank} [ A_{C}, A_{L}, A_{V} ] = n_{C}+n_{L}+n_{V}, \quad\hbox{rank} [ A_{L}, A_{R}, A_{V} ]=n_{\eta}. $$

  (3.12)

Then the MNA system (3.3), (3.4) is asymptotically stable.

Conditions (3.11) are equivalent to the absence of LV-loops and CLI-cutsets (except maybe for LI-cutsets), whereas (3.12) implies that the circuit does not contain CLV-loops (except maybe for CV-loops) and CI-cutsets.

If system (3.3) is asymptotically stable, then the ${{\mathbb{H}}_\infty}$-norm of its transfer function G is defined as ${\|{\bf G}\|_{{\mathbb{H}}_\infty}=\sup\nolimits_{\omega\in{\mathbb{R}}}\|{\bf G}(i\omega)\|}$, where $\|\cdot\|$ denotes the spectral matrix norm.

2.2 Passivity and Positive Realness

Passivity is a most basic property of circuit equations. Generally speaking, passivity means that the system does not produce energy. More precisely, system (3.3) is passive if

$$ \int\limits_0^t u(\tau)^Ty(\tau) d\tau \geq 0 $$

(3.13)

for all $t\geq 0$ and all admissible u such that u ^T y is locally integrable. For a circuit element with a voltage v and a current j, condition (3.13) implies that the storage energy of this element defined as

$$ \int\limits_0^t v(\tau)^Tj(\tau) d\tau $$

is always nonnegative. Thus, capacitors, resistors and inductors with nonnegative element values are passive. Furthermore, interconnection of a finite number of passive circuit components yields a passive network [1].

It is well known in network theory [1] that the DAE system (3.3) is passive if and only if its transfer function G(s) = C(sE − A)⁻¹ B + D is positive real, i.e., G is analytic in ${{\mathbb{C}}_+}$ and ${\bf G}(s)+{\bf G}(s)^*\geq 0$ for all ${s\in{\mathbb{C}}_+}$. Using the Weierstrass canonical form (3.5) and (3.10), the transfer function of (3.3) can be additively decomposed as

$$ {\mathbf{G}}(s)={{\mathbf{G}}}_{sp}(s)+M_0+sM_1+\cdots+s^{\mu-1}M_{\mu-1}, $$

where ${\bf G}_{sp}(s)=C_f(sI-A_f)^{-1}B_f$ is the strictly proper part of ${\bf G}, M_0=D-C_\infty B_\infty$ and $M_k=-C_\infty E_\infty^k B_\infty$ for $k\geq 1$. One can show that G is positive real if and only if its proper part ${\bf G}_p(s)={\bf G}_{sp}(s)+M_0$ is positive real, $M_1=M_1\geq 0$ and M _k  = 0 for k > 1, see [1].

The following proposition gives sufficient conditions for system (3.3), (3.4) to be stable and passive.

Proposition 3

If Assumptions (A1)–(A3) are fulfilled and the matrices${{\mathcal{C}}}$and${{\mathcal{L}}}$are symmetric, then the MNA system (3.3), (3.4) is stable and passive.

Proof

The facts that the pencil λE − A in (3.4) has no finite eigenvalues in ${{\mathbb{C}}_+}$ and the transfer function G(s) = C(sE − A)⁻¹ B of (3.3), (3.4) is positive real have been proved in [61, 66], respectively. Analogously, we can show that (sE − A)⁻¹ is also positive real. Hence, the purely imaginary eigenvalues of λE − A are semi-simple [1, Theorem 2.7.2]. Thus, the MNA system (3.3), (3.4) is stable and passive. $\square$

2.3 Contractivity and Bounded Realness

An important class of dynamical systems are contractive systems. System (3.3) is called contractive if

$$ \int_0^t (\|u(\tau)\|^2-\|y(\tau)\|^2) d\tau \geq 0 $$

(3.14)

for all $t\geq 0$ and all admissible u such that u and y are both square integrable. The integral in (3.14) expresses the difference between the input and output energy of the system. One can show that (3.3) is contractive if and only if its transfer function G is bounded real, i.e., G is analytic in ${{\mathbb{C}}}_+$ and $I-{\bf G}(s)^*{\bf G}(s)\geq 0$ for all $s\in{\mathbb{C}}_+$, see [1]. For the asymptotically stable system (3.3), contractivity is equivalent to the condition $\|{\bf G}\|_{{\mathbb{H}}_{\infty}}\leq 1$ that justifies the name ‘contractive’. Note that the bounded real transfer function is necessarily proper.

Positive real and bounded real square transfer functions are related to each other via a Moebius transformation defined as

$$ {\fancyscript{M}}({{\mathbf{G}}})(s)=(I-{{\mathbf{G}}}(s))(I+{{\mathbf{G}}}(s))^{-1}. $$

The transfer function G is positive real if and only if the Moebius-transformed function $\hat{\mathbf{G}}(s)=\fancyscript{M}({\mathbf{G}})(s)$ is bounded real [1]. For system (3.3) with nonsingular I + D, the function $\hat{\mathbf{G}}(s)$ can be represented as $\hat{{{\bf G}}}(s)=\hat{C}(s\hat{E} -\hat{A})^{-1}\hat{B}+\hat{D}$, where

$$ \begin{array}{l} \hat{E}=E, \quad \hat{A}=A-B(I+D)^{-1}C, \quad \hat{B} = -\sqrt{2}B(I+D)^{-1}, \\ \hat{C}=\sqrt{2}(I+D)^{-1}C, \quad \hat{D}=(I-D)(I+D)^{-1}. \\ \end{array} $$

For the MNA matrices as in (3.4), we have

$$\begin{aligned} \hat{E} &=\left[\begin{array}{lll} A_{C}{{\mathcal C}} A_{C}^T&0 & 0\\ 0&{\mathcal L} & 0\\ 0& 0& 0 \\ \end{array}\right],\quad \hat{A}=\left[\begin{array}{lll} -A_{R}{{\mathcal G}} A_{R}^T-A_{I} A_{I}^T&-A_{L} & -A_{V} \\ A_{L}^T & 0 & 0 \\ A_{V}^T & 0 & -I\\ \end{array}\right],\\ \hat{B} &= \sqrt{2}\left[\begin{array}{ll} A_{I} & 0 \\ 0 & 0 \\ 0 & I \\ \end{array}\right] =-\hat{C}^T , \quad \hat{D}=I. \end{aligned} $$

(3.15)

It has been shown in [64] that under Assumptions (A1)–(A3) the pencil $\lambda \hat{E}-\hat{A}$ in (3.15) is of index at most two. It is equal to one if and only if $\hbox{rank}[ A_{C}, A_{R}, A_{I}, A_{V} ]=n_\eta$. This condition means that the circuit does not contain L-cutsets.

2.4 Reciprocity

Another relevant property of circuit equations is reciprocity. We call a matrix ${S\in{\mathbb{R}}^{m,m}}$ a signature if S is diagonal and S ² = I _m . System (3.3) is reciprocal with an external signature ${S_{\rm ext}\in{\mathbb{R}}^{m,m}}$ if its transfer function satisfies ${{\bf G}}(s)=S_{\rm ext}{{\bf G}}(s)^TS_{\rm ext}$ for all ${s\in{\mathbb{C}}}$. The following proposition shows that the symmetry of ${{\mathcal{C}}}$, ${{\mathcal {L}}}$ and ${{\mathcal{G}}}$ guarantees the reciprocity of system (3.3), (3.4).

Proposition 4

[62] Let Assumptions (A1)–(A3) be fulfilled and let the matrices ${{\mathcal{C}}}$, ${{\mathcal{L}}}$ and ${{\mathcal{G}}}$ be symmetric. Then the MNA system (3.3), (3.4) is reciprocal with the external signature $S_{\rm ext}=\hbox{diag}(I_{n_I},-I_{n_V})$.

3 Balancing-Related Model Reduction

The aim of model order reduction for circuit equations is to approximate the DAE system (3.3), (3.4) with a reduced-order model

$$ \begin{aligned} \tilde{E} \dot{\tilde{x}}(t) &= \tilde{A} \tilde{x}(t)+ \tilde{B} u(t), \\ \tilde{y}(t) &= \tilde{C} \tilde{x}(t) + \tilde{D} u(t), \end{aligned} $$

(3.16)

where $\tilde{E}$, $\tilde{A} \in {\mathbb{R}}^{\ell, \ell}$, $\tilde{B} \in {\mathbb{R}}^{\ell, m}$, $\tilde{C}\in {\mathbb{R}}^{m, \ell}$, $\tilde{D}\in{\mathbb{R}}^{m,m}$ and ℓ ≪ n. It is required for the approximate system (3.16) to preserve physical properties like stability, passivity and reciprocity. Such a system can then be synthesized as an electrical circuit in an standard netlist format, e.g., [62, 84] and Chap. 12 of this volume, that is often required in the industrial circuit simulators. It is also important to have a small approximation error $\tilde{y}-y$ or $\tilde{{\bf G}}-{\bf G}$, where $\tilde{{\bf G}}(s)=\tilde{C}(s\tilde{E}-\tilde{A})^{-1}\tilde{B}+\tilde{D}$. In the ideal case, we would like to have a computable error bound that allows us to approximate (3.3) to a given accuracy and makes model reduction fully automatic.

Most of the model reduction methods for linear dynamical systems are based on the projection of the system onto lower dimensional subspaces. In this case, the system matrices of the reduced-order model (3.16) have the form

$$ \tilde{E}={W}^T{E} {T},\quad \tilde{A}={W}^T{A} {T},\quad \tilde{B}={W}^T{B}, \quad \tilde{C}={C} {T}, $$

(3.17)

where the projection matrices W, $T\in{\mathbb{R}}^{n,\ell}$ determine the subspaces of interest. For example, in modal model reduction the columns of W and T span, respectively, the left and right deflating subspaces of the pencil λE − A corresponding to the dominant eigenvalues, e.g., [25, 50]. In the moment matching approximation, one chooses the projection matrices W and T whose columns form the bases of certain Krylov subspaces associated with (3.3), e.g., [4, 30].

3.1 Balanced Truncation Model Reduction

Balanced truncation also belongs to the projection-based model reduction techniques. This method consists in transforming the dynamical system into a balanced form whose controllability and observability Gramians are both equal to a diagonal matrix. Then a reduced-order model (3.16), (3.17) is obtained by projecting (3.3) onto the subspaces corresponding to the dominant diagonal elements of the balanced Gramians. This idea goes back to [54] and has been extended over the years in different directions by many authors, e.g., [11, 14, 26, 35, 39, 52, 53, 55, 58, 60, 74, 77].

For standard state space systems with E = I, the balanced truncation model reduction method makes use of the dual Lyapunov equations

$$ AG_c + G_c A^T = -BB^T,\quad A^TG_o + G_o A = -C^TC. $$

If all eigenvalues of the matrix A have negative real part, then these equations have unique symmetric, positive semidefinite solutions G _c and G _o known as the controllability and observability Gramians, respectively. One can show that all eigenvalues of the product $G_c G_o$ are real and nonnegative. The square roots of these eigenvalues, denoted by σ _j , are called the Hankel singular values of system (3.3) with E = I. Such a system is balanced if $G_c=G_o=\hbox{diag}(\sigma_1, \ldots,\sigma_n)$. If the system is controllable and observable, then the Gramians G _c and G _o are both positive definite. In this case, there exists a balancing state space transformation such that the Gramians of the transformed system become equal and diagonal with the Hankel singular values on the diagonal. Then the reduced-order model is obtained by truncating the states corresponding to the small Hankel singular values. Such states are simultaneously difficult to reach and to observe, since they have a small impact on the energy transfer from input to output, see [35, 53] for details.

The balanced truncation model reduction approach can be extended to system (3.3) with E ≠ I. If E is nonsingular, then the Gramians are defined as unique symmetric, positive semidefinite solutions of the generalized Lyapunov equations

$$ AG_c E^T + EG_c A^T = -BB^T, \quad A^TG_o E + E^TG_o A = -C^TC, $$

(3.18)

provided the pencil λE − A is c-stable. However, for singular E, these equations cannot be used any more to determine the Gramians for the DAE system (3.3). As the following example shows, the generalized Lyapunov equations (3.18) with singular E may not have solutions even if λE − A is c-stable. Moreover, if the solutions of (3.18) exist, they are always nonunique, see [73] for detailed discussions.

Example 1

Consider the simple RL circuit shown in Fig. 3.1. This circuit is described by the DAE system (3.3) with

$$ \begin{aligned} E &= \left[\begin{array}{llll} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & {\mathcal L} & 0 \\ 0 & 0 &0 & 0 \\ \end{array}\right], \quad A = \left[\begin{array}{llll} 0 & 0 & -1 & 1 \\ 0 & -1/{\mathcal R}& 1 & 0 \\ 1 & -1 & 0 & 0 \\ -1 & 0 & 0 & 0\\ \end{array} \right], \\ B^T &=\left[\begin{array}{llll} 0, & 0, & 0, & -1 \end{array}\right]=C. \end{aligned} $$

The pencil λE − A has only one finite eigenvalue ${\lambda=-{\mathcal{R}}/{\mathcal{L}}<0}$. However, the generalized Lyapunov equations (3.18) are not solvable.

Fig. 3.1

A simple RL circuit

An extension of the balanced truncation method to DAEs based on projected Lyapunov equations has been presented in [52, 74]. Unlike the standard state space case, the DAE system (3.3) has two pairs of the Gramians, one pair for the slow subsystem (3.8a, b) and the other pair for the fast subsystem (3.9a, b). If (3.3) is asymptotically stable, then the proper controllability and observability Gramians G _pc and G _po of (3.3) are defined as unique symmetric, positive semidefinite solutions of the projected generalized continuous-time Lyapunov equations

$$ E G_{pc} A^T+A G_{pc} E^T =-P_l BB^TP_l^T, \quad G_{pc}=P_r G_{pc} P_r^T, $$

(3.19)

$$ E^TG_{po} A+A^TG_{po} E=-P_r^TC^T\!CP_r , \quad G_{po}=P_l^TG_{po} P_l, $$

(3.20)

where P _l and P _r are the spectral projectors onto the left and right deflating subspaces of the pencil λE − A corresponding to the finite eigenvalues along the left and right deflating subspaces corresponding to the eigenvalue at infinity. Using the Weierstrass canonical form (3.5), these projectors can be represented as

$$ P_r=T_r^{-1}\left[\begin{array}{ll} I & 0 \\ 0 & 0 \end{array}\right]T_r , \quad P_l=T_l \left[\begin{array}{ll} I & 0 \\ 0 & 0 \end{array}\right]T_l^{-1}. $$

Furthermore, the improper controllability and observability Gramians G _ic and G _io of system (3.3) are defined as unique symmetric, positive semidefinite solutions of the projected generalized discrete-time Lyapunov equations

$$ A G_{ic}A^T - E G_{ic}E^T = Q_l BB^TQ_l^T, \quad G_{ic}=Q_r G_{ic}Q_r^T, $$

(3.21)

$$ A^TG_{io}A - E^TG_{io}E = Q_r^TC^T\!CQ_r , \quad G_{io}=Q_l^TG_{io}Q_l, $$

(3.22)

where $Q_l=I-P_l$ and $Q_r=I-P_r$ are the complementary projectors. Note that unlike generalized Lyapunov equations considered in [42, 48, 76], the existence and uniqueness results for the projected Lyapunov equations (3.19)–(3.22) can be stated independently of the index of the pencil λE − A, see [73].

Using the proper and improper Gramians, we can define the proper and improper Hankel singular values that characterize the importance of state variables in the slow and fast subsystems (3.8), and (3.9), respectively. Let n _f be the dimension of the deflating subspaces of λE − A corresponding to the finite eigenvalues. Then the proper Hankel singular values σ _j of system (3.3) are defined as the square roots of the largest n  _f eigenvalues of the matrix $G_{pc}E^TG_{po}E$, and the improper Hankel singular values θ _j are defined as the square roots of the largest $n_\infty=n-n_{\!f}$ eigenvalues of the matrix $G_{ic}A^TG_{io}A$. We assume that the proper and improper Hankel singular values are ordered decreasingly. System (3.3) is balanced if the Gramians satisfy

$$ \begin{aligned}G_{pc}&=G_{po}={\rm diag}(\Upsigma, 0 ) \quad\hbox{with}\quad \Upsigma={\rm diag}(\sigma_1,\ldots,\sigma_{n_{\!f}}), \\ G_{ic}&=G_{io}={\rm diag}( 0,\Uptheta ) \quad\hbox{with}\quad \Uptheta ={\rm diag}(\theta_1,\ldots,\theta_{n_\infty}). \end{aligned}$$

States of the balanced system corresponding to the small proper Hankel singular values are less involved in the energy transfer from inputs to outputs, and, therefore, they can be truncated without changing the system properties significantly. Furthermore, we can remove the states of the balanced system corresponding to the zero improper Hankel singular values. Such states are uncontrollable and unobservable at infinity and do not influence the input–output relation. However, if we truncate the states that correspond to the non-zero improper Hankel singular values, even if they are small, then the approximation may be inaccurate. These states are subject to constraints, and their elimination may lead to undesirable disturbances in the approximate system and physically meaningless results.

Example 2

Consider the DAE system (3.3) with

$$ E=\left[\begin{array}{lll} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{array}\right], \quad A=I_3, \quad B=\left[\begin{array}{l} 10 \\ 0.1 \\ 0 \\ \end{array}\right], \quad C^T=\left[\begin{array}{l} 0.04 \\ 30 \\ 1 \\ \end{array}\right]. $$

(3.23)

Since E is nilpotent, this system has only the improper Hankel singular values given by θ₁ = 3.4, $\theta_2=4.7\times 10^{-6}$, θ₃ = 0. The truncation of the state corresponding to the Hankel singular value θ₃ = 0 results in the reduced-order model

$$ \begin{aligned} \left[\begin{array}{ll} 1.18 & 1.18 \\ -1.18 & -1.18 \\ \end{array}\right] \dot{\tilde{x}}(t)&= \left[\begin{array}{ll} 10^3 & 0 \\ 0 & 10^3 \\ \end{array}\right] \tilde{x}(t) + \left[\begin{array}{l} 1.84\times 10^{3} \\ 2.25\times 10^{-3} \\ \end{array}\right] u(t), \\ \tilde{y}(t)&= [1.84\times 10^{3}, -2.25\times 10^{-3} ]\tilde{x}(t).\\ \end{aligned} $$

(3.24)

Figure 3.2a shows the output functions of the original and the reduced-order systems with the input $u(t)=\sin(t)$. They coincide since both systems have the same transfer function. However, if we truncate one more state corresponding to the second Hankel singular value, which is relatively small, we obtain the standard state space system

$$ \dot{\tilde{x}}(t) = 850 \tilde{x}(t) + 1567 u(t), \quad \tilde{y}(t)=1.84 \tilde{x}(t). $$

(3.25)

This system is unstable, and, as Fig. 3.2b demonstrates, its output has nothing in common with the output of the original system.

Fig. 3.2

(a) The output functions of the original system (3.3), (3.23) and the reduced-order system (3.24); (b) the output of the reduced-order system (3.25). In both cases, the input is $u(t)=\sin(t)$

We summarize the balanced truncation model reduction method for DAEs in Algorithm 1. For this method, we have the following a priori error bound.

$$ \|\tilde{y}-y\|_{{{\mathbb{L}}}_2}\leq \|\tilde{{{\mathbf G}}}- {{\mathbf G}}\|_{{{\mathbb{H}}}_\infty}\|u\|_{{{\mathbb{L}}}_2}\leq 2(\sigma_{\ell_{\!f}+1}+\cdots+\sigma_{n_{\!f}})\|u\|_{{{\mathbb{L}}}_2} $$

that allows an adaptive choice of the order of the approximate model. Furthermore, the resulting reduced-order system (3.16) is asymptotically stable and its index does not exceed the index of (3.3). If ${{\mathcal{C}}}$, ${{\mathcal{L}}}$ and ${{\mathcal{G}}}$ in (3.4) are symmetric, i.e., (3.3), (3.4) is reciprocal with the external signature $S_{\rm ext}$ as in Proposition 4, then the reduced-order model computed by Algorithm 1 is also reciprocal with the same signature. Unfortunately, the Lyapunov-based balanced truncation method does not, in general, ensure the preservation of passivity. However, for special reciprocal circuits such as RC and RL networks, Algorithm 1 can be modified for computing a passive reduced-order model, see [65] for details.

Algorithm 1

Balanced truncation model reduction for DAEs.

Given G = (E, A, B, C, D), compute a reduced-order model $\tilde{{{\bf G}}}=( \tilde{E}, \tilde{A}, \tilde{B}, \tilde{C}, \tilde{D} )$.

• 1. Compute the Cholesky factors R _p and L _p of the proper Gramians $G_{pc} = R_p R_p^T$ and $G_{po} = L_p L_p^T$ that satisfy the projected Lyapunov equations (3.19) and (3.20), respectively.

• 2. Compute the Cholesky factors R _i and L _i of the improper Gramians $G_{ic} = R_i R_i^T$ and $G_{io} = L_i L_i^T$ that satisfy the projected Lyapunov equations (3.21) and (3.22), respectively.

• 3. Compute the singular value decomposition $L_p^TER_p = [ U_1, U_2 ] \hbox{diag}(\Upsigma_1, \Upsigma_2)[ V_1, V_2 ]^T,$ where the matrices $\left[U_1, U_2\right]$ and $\left[ V_1, V_2 \right]$ have orthonormal columns, $\Upsigma_1=\hbox{diag}(\sigma_1,\ldots,\sigma_{\ell_{\!f}})$ and $\Upsigma_2=\hbox{diag}(\sigma_{\ell_{\!f}+1},\ldots,\sigma_{n_{\!f}})$.

• 4. Compute the singular value decomposition $L_i^TAR_i =U_3 \Uptheta V_3^T$, where U ₃ and V ₃ have orthonormal columns and $\Uptheta=\hbox{diag}(\theta_1,\ldots,\theta_{\ell_\infty})$ is nonsingular.

• 5. Compute the reduced-order system $( \tilde{E}, \tilde{A}, \tilde{B}, \tilde{C}, \tilde{D} ) = ( W^TET, W^TAT, W^TB, CT, D )$ with $W=[ L_pU_1\Upsigma_1^{-1/2}, L_iU_3\Uptheta^{-1/2} ]$ and $T=[ R_pV_1 \Upsigma_1^{-1/2}, R_iV_3\Uptheta^{-1/2} ]$.

3.2 Positive Real Balanced Truncation

In this section, we describe passivity-preserving model reduction for general RCL circuits based on positive real balancing.

Passivity of the DAE system (3.3) can be characterized via the projected positive real Lur’e equations

$$ \begin{aligned} AX E^T+EX A^T&=-K_{c} K_{c}^T,\quad X = P_r X P_r^T\geq 0,\\ EX C^T-P_lB&=-K_{c} J_c^T,\quad M_0 +M_0^T=J_c J_c^T \\ \end{aligned} $$

(3.26)

and

$$ \begin{aligned} A^TY E+E^TY A&=-K_{o}^TK_{o} ,\quad Y=P_l^TY P_l \geq 0,\\ E^TY B-P_r^TC^T&=-K_{o}^TJ_o,\quad M_0 +M_0^T=J_o^TJ_o \\ \end{aligned} $$

(3.27)

with unknowns ${X\in{\mathbb{R}}^{n,n}}$, ${K_{c}\in{\mathbb{R}}^{n,m}}$, ${J_c\in{\mathbb{R}}^{m,m}}$ and ${Y\in{\mathbb{R}}^{n,n}}$, ${K_{o}\in{\mathbb{R}}^{m,n}}$, ${J_o\in{\mathbb{R}}^{m,m}}$, respectively. Such equations are known in the literature also as Kalman–Yakubovich–Popov equations [40]. Similarly to [64, Theorem 4.1], one can show that if the MNA system (3.3), (3.4) is passive, then (3.26) and (3.27) are solvable. Conversely, solvability of the projected Lur’e equations (3.26) and (3.27) together with the conditions $M_1=M_1^T\geq0$ and M _k  = 0 for k > 1 implies that (3.3) is passive.

Remark 1

Note that for a general DAE system, passivity alone does not guarantee the existence of the solution of the projected Lur’e equations. For such a system, in addition, R-minimality conditions

$$ \hbox{rank}[ \lambda E-A,\; B ]=n, \quad \hbox{rank}[ \lambda E^T-A^T,\; C^T ]=n \quad \hbox{for all}\;\lambda\in{{\mathbb{C}}} $$

(or other weaker conditions) have to be assumed [23, 29, 47, 62].

The projected Lur’e equations (3.26) and (3.27) have, in general, many symmetric solutions X and Y that can be ordered with respect to the Loewner ordering in the set of symmetric matrices. The minimal solutions X _pr and Y _pr that satisfy $0\leq X_{pr}\leq X$ and $0\leq Y_{pr}\leq Y$ for all symmetric solutions X and Y of (3.26) and (3.27), respectively, are called the positive real controllability and observability Gramians of (3.3). System (3.3) is called positive real balanced if $X_{pr}=Y_{pr}=\hbox{diag}(\Upxi,0)$ with $\Upxi=\hbox{diag}(\xi_1,\ldots,\xi_{n_{\!f}})$. The values ξ _j ordered decreasingly are called the positive real characteristic values of (3.3). Similarly to Lyapunov-based balanced truncation, the reduced-order system (3.16) can be computed by projecting onto the subspaces corresponding to the dominant positive real characteristic values and non-zero improper Hankel singular values. Note that if system (3.3) has a proper transfer function, then solving the projected discrete-time Lyapunov equations (3.21) and (3.22) can be avoided. The positive real balanced truncation method for such a system is summarized in Algorithm 2. It can be shown that the resulting reduced-order system is passive, and we have the error bound

$$ \|\tilde{{{\mathbf G}}}-{{\mathbf G}}\|_{{{\mathbb{H}}}_\infty} \leq 2\left\|(M_0 +M_0^T)^{-1}\right\|\|{{\mathbf G}}_0\|_{{{\mathbb{H}}}_\infty} \|\tilde{{{\mathbf G}}}_0\|_{{{\mathbb{H}}}_\infty} (\xi_{\ell_{\!f}+1}+\cdots+\xi_{n_{\!f}}) $$

(3.28)

with ${{\bf G}}_0={{\bf G}}+M_0^T$ and $\tilde{{{\bf G}}}_0=\tilde{{{\bf G}}}+M_0^T$, see [9, 63]. Note that this error bound requires the computation of the ${{\mathbb{H}}_\infty}$-norm of G ₀, which is expensive for large-scale systems. If ℓ _f is chosen in Algorithm 2 such that

$$ 4\left\|(M_0 +M_0^T)^{-1}\right\|\|\tilde{{{\mathbf G}}}_0 \|_{{{\mathbb{H}}}_\infty} (\xi_{\ell_{\!f}+1}+\cdots+\xi_{n_{\!f}})<1, $$

then bound (3.28) can be simplified to

$$ \|\tilde{{{\mathbf G}}}-{{\mathbf G}}\|_{{{\mathbb{H}}}_\infty}\leq 4\left\|(M_0 +M_0^T)^{-1}\right\|\|\tilde{{{\mathbf G}}}_0\|_{{{\mathbb{H}}}_\infty}^2 (\xi_{\ell_{\!f}+1}+\cdots+\xi_{n_{\!f}}), $$

(3.29)

where only the evaluation of the ${{\mathbb{H}}_\infty}$-norm of the reduced-order system $\tilde{{{\bf G}}}_0$ is required.

Algorithm 2

Positive real balanced truncation for DAEs with a proper transfer function.

Given passive G = (E, A, B, C, D), compute a reduced-order system $\tilde{{{\bf G}}}=( \tilde{E}, \tilde{A}, \tilde{B}, \tilde{C}, \tilde{D} ).$

• 1. Compute the matrix $M_0=C(s_0E-A)^{-1}Q_lB+D$ with s ₀ ∈ (0,∞).

• 2. Compute the Cholesky factors R and L of the positive real Gramians X _pr  = RR ^T and Y _pr  = LL ^T that are the minimal solutions of the projected positive real Lur’e equations (3.26) and (3.27).

• 3. Compute the singular value decomposition $L^TER = [ U_1, U_2 ] \hbox{diag}(\Upxi_1, \Upxi_2)[ V_1, V_2 ]^T$, where the matrices $\left[U_1, U_2 \right]$ and $\left[ V_1, V_2 \right]$ have orthonormal columns, $\Upxi_1=\hbox{diag}(\xi_1,\ldots,\xi_{\ell_{\!f}})$ and $\Upxi_2=\hbox{diag}(\xi_{\ell_{\!f}+1},\ldots,\xi_{n_{\!f}})$.

• 4. Compute the reduced-order system

  $$ {\tilde{E}}= \left[\begin{array}{ll} I & 0 \\ 0 & 0 \end{array}\right],\quad {\tilde{A}}= \left[\begin{array}{ll} W_1^T A T_1 & 0\\ 0 & I , \end{array}\right],\quad {\tilde{B}}=\left[\begin{array}{l} W_1^TB \\ B_2 \end{array}\right],\quad {\tilde{C}}=\left[CT_1, C_2\right], \quad {\tilde{D}}=D, $$

  where $W_1=LU_1 \Upxi_1^{-1/2}$, $T_1=RV_1 \Upxi_1^{-1/2}$, and B ₂ and C ₂ are chosen such that $D-M_0=C_2 B_2$.

If $D_0=M_0 +M_0^T$ is nonsingular, then the projected Lur’e equations (3.26) and (3.27) can be written as the projected positive real Riccati equations

$$ \begin{aligned} AX E^T+EX A^T+(EX C^T-P_lB)D_0^{-1}(EX C^T-P_lB)^T&=&0,\quad X &=& P_r X P_r^T, \end{aligned} $$

(3.30)

$$ \begin{aligned} A^TY E+E^TYA+(B^TYE-CP_r)^TD_0^{-1}(B^TY E-CP_r)&=&0,\quad Y&=&P_l^TY P_l . \end{aligned} $$

(3.31)

The numerical solution of these equations will be discussed in Sect. 3.4.2. The major difficulty in solving these equations is that the spectral projectors P _r and P _l are required. They can be computed by the matrix chain approach from [51]. In the large-scale setting, however, it would be beneficial to have an explicit representation for P _r and P _l as it has been done in [75] for some other structured DAEs arising in computational fluid dynamics and multibody systems. Such a representation in terms of the incidence matrices is currently under investigation.

3.3 Passivity-Preserving Model Reduction Via Bounded Real Balanced Truncation

Another passivity-preserving model reduction approach presented first in [63] is based on the bounded real balanced truncation model reduction method applied to the Moebius-transformed system $\hat{{{\bf G}}}={\cal M}({{\bf G}})=({\hat{E}}, {\hat{A}}, {\hat{B}}, {\hat{C}}, {\hat{D}})$ as in (3.15). For the MNA equations (3.3), (3.4), where ${{\mathcal{G}}}$ is positive definite and both ${{\mathcal{L}}}$ and ${{\mathcal{C}}}$ are symmetric and positive definite, it has been shown in [64] that the projected bounded real Lur’e equations

$$ \begin{aligned} &{\hat{A}}X {\hat{E}}^T+{\hat{E}}X {\hat{A}}^T+{\hat{P}}_l{\hat{B}}{\hat{B}}^T{\hat{P}}_l^T = - K_c K_c^T, &\quad X={\hat{P}}_r X {\hat{P}}_r^T\geq 0, \\ {\hat{E}}X{\hat{C}}^T-{\hat{P}}_l{\hat{B}}{\hat{M}}_0^T=-K_c J_c^T, \quad I-{\hat{M}}_0 {\hat{M}}_0^T=J_c J_c^T \\ \end{aligned} $$

(3.32)

and

$$ \begin{aligned} &{\hat{A}}^TY{\hat{E}}+{\hat{E}}^TY{\hat{A}}+ {\hat{P}}_r^T{\hat{C}}^T{\hat{C}}{\hat{P}}_r =- K_o^TK_o , &\quad Y={\hat{P}}_l^TY {\hat{P}}_l \geq 0, \\ -{\hat{E}}^TY{\hat{B}}+{\hat{P}}_r^T{\hat{C}}^T{\hat{M}}_0= -K_o^TJ_o , \quad I-{\hat{M}}_0^T{\hat{M}}_0 =J_o^T J_o \\ \end{aligned} $$

(3.33)

are solvable for ${X\in{\mathbb{R}}^{n,n}, K_c\in{\mathbb{R}}^{n,m}}$, ${J_c\in{\mathbb{R}}^{m,m}}$ and ${Y\in{\mathbb{R}}^{n,n}}$, ${K_o\in{\mathbb{R}}^{m,n}}$, ${J_o\in{\mathbb{R}}^{m,m},}$ respectively. Here, ${\hat{P}}_r$ and ${\hat{P}}_l$ are the spectral projectors onto the right and left deflating subspaces of $\lambda {\hat{E}}-{\hat{A}}$ corresponding to the finite eigenvalues along the right and left deflating subspaces corresponding to the eigenvalue at infinity, and ${\hat{M}}_0=\lim_{s\to\infty}\hat{C}(s\hat{E}-\hat{A})^{-1}\hat{B}+\hat{D}.$ The minimal solutions X _br and Y _br satisfying $0\leq X_{br}\leq X$ and $0\leq Y_{br}\leq Y$ for all symmetric solutions X and Y of (3.32) and (3.33), respectively, are called the bounded real controllability and observability Gramians of system $\hat{{{\bf G}}}.$ This system is bounded real balanced if $X_{br}=Y_{br}=\hbox{diag}(\Upgamma,0)$ with $\Upgamma=\hbox{diag}(\gamma_1,\ldots,\gamma_{n_{\!f}}).$ The values γ _j ordered decreasingly are called the bounded real characteristic values of $\hat{{{\bf G}}}$. Truncating the states of $\hat{{{\bf G}}}$ corresponding to small γ _j and applying the Moebius transformation to the obtained contractive reduced-order model, we get a passive reduced-order system $\tilde{{{\bf G}}}$. The resulting passivity-preserving model reduction method for circuit equations is presented in Algorithm 3. For this method, we have the following a priori error bound

$$ \|\tilde{{{\mathbf G}}}-{{\mathbf G}}\|_{{{\mathbb{H}}}_\infty}\leq \frac{\|I+{{\mathbf G}}\|_{{{\mathbb{H}}}_\infty}^2 (\gamma_{\ell_{\!f}+1}+\cdots+\gamma_{n_{\!f}})} {I-\|I+{{\mathbf G}}\|_{{{\mathbb{H}}}_\infty} (\gamma_{\ell_{\!f}+1}+\cdots+\gamma_{n_{\!f}})}, $$

provided ${\|I+{{\bf G}}\|_{{\mathbb{H}}_\infty}(\gamma_{\ell_{\!f}+1}+\cdots+\gamma_{n_{\!f}})<1}$, see [63]. Furthermore, if we choose ℓ _f in Algorithm 3 such that ${2\|I+\tilde{{{\bf G}}}\|_{{\mathbb{H}}_\infty}(\gamma_{\ell_{\!f}+1}+\cdots+\gamma_{n_{\!f}})<1}$, then we obtain the a posteriori error bound

$$ \|\tilde{{{\mathbf G}}}-{{\mathbf G}}\|_{{{\mathbb{H}}}_\infty}\leq 2\|I+\tilde{{{\mathbf G}}}\|_{{{\mathbb{H}}}_\infty}^2 (\gamma_{\ell_{\!f}+1}+\cdots+\gamma_{n_{\!f}}) $$

(3.34)

that is inexpensive to compute.

Algorithm 3

Passivity-preserving model reduction based on bounded real balanced truncation.

Given passive G = (E, A, B, C, 0), compute a reduced-order model $\tilde{{{\bf G}}}=( {\tilde{E}}, {\tilde{A}}, {\tilde{B}}, {\tilde{C}}, 0 ).$

• 1. Compute the Moebius-transformed system $\hat{{{\bf G}}}=(\hat{E}, {\hat{A}}, {\hat{B}}, {\hat{C}}, {\hat{D}})$ as in (3.15).

• 2. Compute the matrix ${\hat{M}}_0={\hat{D}}+{\hat{C}}(s_0{\hat{E}}-{\hat{A}})^{-1}{\hat{Q}}_l{\hat{B}}$ for some s ₀ ∈ (0,∞).

• 3. Compute the Cholesky factors ${\hat{R}}$ and ${\hat{L}}$ of the bounded real Gramians $X_{br} = {\hat{R}}{\hat{R}}^T$ and $Y_{br} = {\hat{L}}{\hat{L}}^T$ that are the minimal solutions of the projected bounded real Lur’e equations (3.32) and (3.33).

• 4. Compute the singular value decomposition ${\hat{L}}^T{\hat{E}}{\hat{R}} = [U_1,U_2] \hbox{diag}(\Upgamma_1, \Upgamma_2)[V_1,V_2]^T$, where the matrices $\left[U_1, U_2\right]$ and $\left[V_1, V_2\right]$ have orthonormal columns, $\Upgamma_1=\hbox{diag}(\gamma_1,\ldots,\gamma_{\ell_{\!f}})$ and $\Upgamma_2=\hbox{diag}(\gamma_{\ell_{\!f}+1},\ldots,\gamma_{n_{\!f}}).$

• 5. Compute the reduced-order system

  $$\begin{aligned} {\tilde{E}}&= \left[\begin{array}{ll} I & 0 \\ 0 & 0 \end{array}\right],\quad {\tilde{A}}=\frac{1}{2}\left[\begin{array}{ll}{2\hat{W}}_1^T A{\hat{T}}_1 &; \sqrt{2} {\hat{W}}_1^TB{\hat{C}}_2 \\ -\sqrt{2} {\hat{B}}_2 C {\hat{T}}_1 &; 2 I-{\hat{B}}_2 {\hat{C}}_2 \end{array}\right],\\ {\tilde{B}}&=\left[\begin{array}{l} {\hat{W}}_1^TB \\ -{\hat{B}}_2/\sqrt{2} \end{array}\right],\quad {\tilde{C}}^T= \left[\begin{array}{l} (C{\hat{T}}_1)^T \\ {\hat{C}}_2^T/\sqrt{2} \end{array}\right], \end{aligned}$$

  where ${\hat{W}}_1={\hat{L}}U_1 \Upgamma_1^{-1/2},$ $\hat{T}_1=\hat{R} V_1 \Upgamma_1^{-1/2},$ and $\hat{B}_2$ and $\hat{C}_2$ are chosen such that $I-\hat{M}_0=\hat{C}_2\hat{B}_2.$

It should be noted that for DAE systems with a proper transfer function, Algorithms 2 and 3 are equivalent in the sense that they provide reduced-order models with the same transfer function.

Using the topological structure of circuit equations, the matrix ${\hat{M}}_0$ and the projector ${\hat{P}}_r$ can be computed in explicit form

$$ \begin{aligned} {\hat{M}}_0 &=& \left[\begin{array}{ll} I-2A_{I}^TQ_{C} H_0^{-1}Q_{C}^T A_{I} & 2A_{I}^TQ_{C} H_0^{-1}Q_{C}^T A_{V} \\ -2A_{V}^TQ_{C} H_0^{-1}Q_{C}^T A_{I} & -I+2A_{V}^TQ_{C} H_0^{-1}Q_{C}^T A_{V} \\ \end{array}\right], \end{aligned} $$

(3.35)

$$ \begin{aligned} {\hat{P}}_r &=& \left[\begin{array}{lll} H_5(H_4 H_2-I) & H_5 H_4 A_{L}H_6 &0 \\ 0 & H_6 & 0 \\ -A_{V}^T(H_4 H_2-I) & -A_{V}^T H_4 A_{L}H_6 & 0 \end{array}\right], \end{aligned} $$

(3.36)

where

$$\begin{aligned} &H_0= Q_{C}^T(A_{R} {\mathcal G} A_{R}^T+A_{I} A_{I}^T+A_{V} A_{V}^T)Q_{C} +Q_{RIV-C}^TQ_{RIV-C},\\ &H_1= P_{CRIV}^TP_{CRIV} +Q_{CRIV}^TA_{L} {{\mathcal S}} A_{L}^TQ_{CRIV} , \\ &H_2=A_{R} {\mathcal G} A_{R}^T+A_{I} A_{I}^T+A_{V} A_{V}^T +A_{L} {{\mathcal S}} A_{L}^TQ_{CRIV} H_1^{-1}Q_{CRIV}^T A_{L} {{\mathcal S}} A_{L}^T,\\ &H_3=A_{C} {\mathcal C} A_{C}^T+Q_{C}^TH_2Q_{C} , \quad\; H_4 = Q_{C} H_3^{-1}Q_{C}^T,\\ &H_5=Q_{CRIV} H_1^{-1}Q_{CRIV}^TA_{L} {{\mathcal S}} A_{L}^T-I, \quad H_6=I-{{\mathcal S}} A_{L}^TQ_{CRIV} H_1^{-1}Q_{CRIV}^TA_{L} ,\\ & Q_{CRIV}\; \hbox{is a projector onto ker} ([A_{C}, A_{R}, A_{I},A_{V} ]^T),\quad P_{CRIV}=I-Q_{CRIV},\\ & Q_{RIV-C}\; \hbox{is a projector onto ker} ([A_{R}, A_{I}, A_{V} ]^TQ_{C}),\\ \end{aligned} $$

see [64] for details. Furthermore, the left projector is given by ${\hat{P}}_l=S_{\rm int}{\hat{P}}_{r,t}^TS_{\rm int}$, where $S_{\rm int}=\hbox{diag}(I_{n_{\eta}},-I_{n_L},-I_{n_V})$ and ${\hat{P}}_{r,t}$ is as $\hat{P}_r$ with ${{\mathcal{G}},{\mathcal {S}}}$ and ${{\mathcal{C}}}$ replaced by ${{\mathcal{G}}^T, {{\mathcal S}}^T}$ and ${{\mathcal{C}}^T,}$ respectively. The projectors $Q_{C}, Q_{CRIV}$ and Q _RIV-C can easily be computed in sparse form using graph search algorithms like breadth-first-search [44]. Although ${\hat{M}}_0$ and ${\hat{P}}_r$ look very complex, their computation is inexpensive if the sparsity of the incidence matrices and Q-projectors is exploited. Due to the space limitation, we omit detailed discussions.

If the circuit contains neither CVI-loops except for C-loops nor LVI-cutsets except for L-cutsets, i.e., if $\hbox{rank} (Q_{C}^T[ A_{I}, A_{V} ])=n_I+n_V$ and $Q_{RC}^T[ A_{I}, A_{V} ]=0$, where Q _RC is a projector onto $\ker([ A_{R}, A_{C} ]^T)$, then both ${\hat{D}}_c=I-{\hat{M}}_0 {\hat{M}}_0^T$ and ${\hat{D}}_o=I-{\hat{M}}_0^T{\hat{M}}_0$ are nonsingular [64], and the projected Lur’e equations (3.32) and (3.33) can be written as the projected bounded real Riccati equations

$$ \begin{aligned} &{\hat{A}}X E^T+EX {\hat{A}}^T+2{\hat{P}}_lBB^T{\hat{P}}_l^T+ 2(EXC^T-{\hat{P}}_l B{\hat{M}}_0^T){\hat{D}}_c^{-1}(EXC^T-{\hat{P}}_l B{\hat{M}}_0^T)^T=0, \\ &X={\hat{P}}_r X {\hat{P}}_r^T, \\ \end{aligned} $$

(3.37)

and

$$ \begin{aligned} &{\hat{A}}^TY E+E^TY{\hat{A}}+2{\hat{P}}_r^TC^TC{\hat{P}}_r + 2(B^TYE-{\hat{M}}_0^TC{\hat{P}}_r)^T{\hat{D}}_o^{-1} (B^TY{\hat{E}}-{\hat{M}}_0^TC{\hat{P}}_r)=0, \\ &Y={\hat{P}}_l^TY\hat{P}_l . \\ \end{aligned} $$

(3.38)

The numerical solution of these equations will be considered in Sect. 3.4.2.

3.4 Balanced Truncation for Reciprocal Circuit Equations

For reciprocal circuits with symmetric ${{\mathcal{C}},}$ ${{\mathcal {L}}}$ and ${{\mathcal{G}},}$ we can further exploit the structure of the system matrices in (3.4) in order to reduce the computational complexity of Algorithms 2 and 3. In the sequel, we consider Algorithm 3 only. The other one can be modified analogously.

Consider the reciprocal system (3.3), (3.4), where ${{\mathcal{C}},}$ ${{\mathcal{L}}}$ and ${{\mathcal{G}}}$ are symmetric. Then

$$ {\hat{E}}^T=S_{\rm int} {\hat{E}} S_{\rm int}, \quad {\hat{A}}^T=S_{\rm int} {\hat{A}} S_{\rm int},\quad {\hat{B}}^T=S_{\rm ext} {\hat{C}} S_{\rm int} $$

with $S_{\rm int}={\hbox{diag}}(I_{n_{\eta}}, -I_{n_{L}}, -I_{n_{V}})$ and $S_{\rm ext}={\hbox{diag}}(I_{n_{I}}, -I_{n_{V}}).$ Therefore, we have

$$ \begin{aligned} {\hat{P}}_l&=S_{\rm int} {\hat{P}}_r^TS_{\rm int}, \\ Y_{br}&=S_{\rm int} X_{br} S_{\rm int}=S_{\rm int} {\hat{R}} {\hat{R}}^T S_{\rm int}^T={\hat{L}}{\hat{L}}^T. \\ \end{aligned} $$

(3.39)

Since ${\hat{L}}^T{\hat{E}}{\hat{R}}={\hat{R}}^TS_{\rm int}{\hat{E}}{\hat{R}}$ and $(I-{\hat{M}}_0)S_{\rm ext}$ are both symmetric, the characteristic values γ _j and the matrices ${\hat{B}}_2$ and ${\hat{C}}_2$ can be determined from the eigenvalue decompositions of ${\hat{R}}^TS_{\rm int}{\hat{E}}{\hat{R}}$ and $(I-{\hat{M}}_0)S_{\rm ext}$ instead of a more expensive singular value decomposition. We summarize the resulting passivity-preserving balanced truncation method for reciprocal electrical circuits (PABTEC) in Algorithm 4. Note that this method also preserves reciprocity in the reduced-order model, see [64].

Algorithm 4

Passivity-preserving balanced truncation for electrical circuits (PABTEC).

Given passive G = (E, A, B, C, 0) with the system matrices as in (3.4), compute a reduced-order model $\tilde{{{\bf G}}}=( {\tilde{E}}, {\tilde{A}}, {\tilde{B}}, {\tilde{C}}, 0 )$.

• 1. Compute the Cholesky factor ${\hat{R}}$ of the bounded real Gramian $X_{br} = {\hat{R}}{\hat{R}}^T$ that is the minimal solution of the projected Lur’e equation (3.32), where ${\hat{E}}$, ${\hat{A}}$, ${\hat{B}}$ and ${\hat{C}}$ are as in (3.15), the projectors ${\hat{P}}_r$ and ${\hat{P}}_l$ are given in (3.36) and (3.39), respectively, and ${\hat{M}}_0$ is as in (3.35).

• 2. Compute the eigenvalue decomposition ${\hat{R}}^TS_{\rm int}{\hat{E}}{\hat{R}} = [ U_1, U_2 ] \hbox{diag}(\Uplambda_1, \Uplambda_2)[ U_1, U_2 ]^T$, where $\left[ U_1, U_2 \right]$ is orthogonal, $\Uplambda_1={\hbox{diag}}(\lambda_1,\ldots,\lambda_{\ell_{\!f}})$ and $\Uplambda_2=\hbox{diag}(\lambda_{\ell_{\!f}+1},\ldots,\lambda_{n_{\!f}}).$

• 3. Compute the eigenvalue decomposition $(I-M_0)S_{\rm ext}=U_0 \Uplambda_0 U_0^T$, where U ₀ has orthonormal columns and $\Uplambda_0=\hbox{diag}(\hat{\lambda}_1, \ldots, \hat{\lambda}_m)$ is nonsingular.

• 4. Compute the reduced-order system

  $$ {\tilde{E}}=\left[\begin{array}{ll} I & 0 \\ 0 & 0 \end{array}\right], \quad {\tilde{A}}=\frac{1}{2} \left[\begin{array}{ll} 2{\hat{W}}_1^T A{\hat{T}}_1 & \sqrt{2}{\hat{W}}_1^TB{\hat{C}}_2 \\ -\sqrt{2}{\hat{B}}_2 C {\hat{T}}_1 & 2 I-{\hat{B}}_2 {\hat{C}}_2 \end{array}\right], \quad {\tilde{B}}= \left[\begin{array}{l} {\hat{W}}_1^TB \\ -{\hat{B}}_2/\sqrt{2} \end{array}\right], \quad {\tilde{C}}^T= \left[\begin{array}{l} (C{\hat{T}}_1)^T \\ {\hat{C}}_2^T/\sqrt{2} \end{array}\right], $$

  where

  $$ {\hat{W}}_1=S_{\rm int}R U_1 |\Uplambda_1|^{-1/2}, \quad {\hat{T}}_1={\hat{R}} U_1 S_1 |\Uplambda_1|^{-1/2}, \quad {\hat{B}}_2=S_0|\Uplambda_0|^{1/2}U_0^TS_{\rm ext}, \quad {\hat{C}}_2=U_0 |\Uplambda_0|^{1/2}, $$

  with

  $$ \begin{aligned} |\Uplambda_1|&=\hbox{diag}(|\lambda_1|,\ldots,|\lambda_{\ell_{\!f}}|), \quad S_1=\hbox{diag}(\hbox{sign}(\lambda_1),\ldots,\hbox{sign}(\lambda_{\ell_{\!f}})),\\ |\Uplambda_0|&=\hbox{diag}(|\hat{\lambda}_1|, \ldots, |\hat{\lambda}_m|), \quad S_0=\hbox{diag}(\hbox{sign}(\hat{\lambda}_1), \ldots, \hbox{sign}(\hat{\lambda}_m)). \\ \end{aligned} $$

4 Numerical Methods for Matrix Equations

In this section, we consider numerical algorithms for the projected Lyapunov equations (3.19) and (3.20) and the projected Riccati equations (3.30), (3.31) and (3.37), (3.38) developed in [10, 75]. In practice, the numerical rank of the solutions of these equations is often much smaller than the dimension of the problem. Then such solutions can be well approximated by low-rank matrices. Moreover, these low-rank approximations can be determined directly in factored form. Replacing the Cholesky factors of the Gramians in Algorithms 1–4 by their low-rank factors reduces significantly the computational complexity and storage requirements in the balancing-related model reduction methods and makes these methods very suitable for large-scale DAE systems.

4.1 ADI Method for Projected Lyapunov Equations

First, we focus on solving the projected Lyapunov equation

$$ E X A^T+A X E^T=-P_l BB^T\!P_l^T, \quad X=P_r X P_r^T, $$

(3.40)

using the alternating direction implicit (ADI) method. The dual equation can be treated analogously. The ADI method has been first proposed for standard Lyapunov equations [16, 49, 57, 80] and then extended in [75] to projected Lyapunov equations. The generalized ADI iteration for the projected Lyapunov equation (3.40) is given by

$$ \begin{aligned} (E+\tau_k A)X_{k-1/2}A^T + AX_{k-1}(E-\tau_k A)^T& = -P_l BB^TP_l^T, \\ (E+\overline{\tau}_k A)X_k^TA^T + AX_{k-1/2}^T(E-\overline{\tau}_k A)^T & = -P_l BB^TP_l^T \\ \end{aligned} $$

(3.41)

with an initial matrix X ₀ = 0 and shift parameters ${\tau_1,\ldots,\tau_k\in{\mathbb{C}}_-}$. If the pencil λE − A is c-stable, then X _k converges towards the solution of the projected Lyapunov equation (3.40). The rate of convergence depends strongly on the choice of the shift parameters. The optimal shift parameters providing the superlinear convergence satisfy the generalized ADI minimax problem

$$ \{\tau_1,\ldots,\tau_q\} = \underset{\{\tau_1,\ldots,\tau_q\}\in{{\mathbb{C}}}_-}{\arg\min} \;\max_{t\in{\scriptstyle {Sp}_{\!f}}\!(E, A)} \frac{{{|(1- \overline{\tau}_1 t)\cdots(1-\overline{\tau}_q t)|}}} {{{|(1+\tau_1 t)\cdots(1+\tau_q t)|}}}, $$

where Sp _f (E, A) denotes the finite spectrum of the pencil λE − A. Similarly to [57], the suboptimal ADI parameters can be obtained from a set of largest and smallest in modulus approximate finite eigenvalues of λE − A computed by an Arnoldi procedure. Other parameter selection techniques developed for standard Lyapunov equations [17, 69, 81] can also be used for the projected Lyapunov equation (3.40).

A low-rank approximation to the solution of the projected Lyapunov equation (3.40) can be computed in factored form $X\approx Z_k Z_k^T$ using a low-rank version of the ADI method (LR-ADI) as presented in Algorithm 5.

Algorithm 5

The generalized LR-ADI for the projected Lyapunov equation.

Given ${E, A\in{\mathbb{R}}^{n,n},}$ ${B\in{\mathbb{R}}^{n,m},}$ projector P _l and shift parameters ${\tau_1,\ldots,\tau_q\in{\mathbb{C}}_-,}$ compute a low-rank approximation $X\approx Z_k Z_k^T$ to the solution of the projected Lyapunov equation (3.40).

• 1. $Z^{(1)} = {\sqrt{-2\hbox{Re}(\tau_1)} (E+\tau_1A)^{-1}P_lB}, \quad Z_1=Z^{(1)}$;

• 2. FOR $k=2,3,\ldots$

  $$ Z^{(k)} ={\sqrt\frac{\hbox{Re}(\tau_k)} {\hbox{Re}(\tau_{k-1})}} \left(I-(\overline{\tau}_{k-1}+\tau_k)(E+\tau_kA)^{-1}A\right)Z^{(k-1)},\quad Z_k = [ Z_{k-1}, Z^{(k)} ]\quad $$

  END FOR

In order to guarantee for the factors Z _k to be real in case of complex shift parameters, we take these parameters in complex conjugate pairs $\{\tau_k,\tau_{k+1}=\overline{\tau}_k\}$. At each iteration we have ${Z_k=[ Z^{(1)}, \ldots, Z^{(k)} ]\in{\mathbb{R}}^{n,mk}}$. To keep the low-rank structure in Z _k for large mk, we can compress the columns of Z _k using the rank-revealing QR factorization [21] as described in [8].

Finally, note that the matrices (E + τ _k A)⁻¹ in Algorithm 5 do not have to be computed explicitly. Instead, we solve linear systems of the form $(E+\tau_kA)x=P_lb$ either by computing (sparse) LU factorizations and forward/backward substitutions or by using iterative Krylov subspace methods [68].

4.2 Newton–Kleinman Method for Projected Riccati Equations

In this section, we consider the numerical solution of the projected Riccati equation

$$ {{\fancyscript{R}}}(X)\equiv EXF^T+ FXE^T+EXH^THXE^T + \Uppi_l QQ^T\Uppi_l^T=0, \quad X=\Uppi_r X\Uppi_r^T, $$

(3.42)

where

$$ \begin{aligned} &F=A-P_lB(M_0 +M_0^T)^{-1}CP_r, \quad H=J_c^{-1}CP_r, \quad Q=BJ_c^{-T}, \\ &M_0 +M_0^T=J_c J_c^T,\quad \Uppi_l=P_l, \quad \Uppi_r=P_r \\ \end{aligned} $$

(3.43)

in the positive real case and

$$ \begin{aligned} F&=A-BC-2{\hat{P}}_lB{\hat{M}}_0^T(I-{\hat{M}}_0 {\hat{M}}_0^T)^{-1}C{\hat{P}}_r,\\ H&=\sqrt{2}J_c^{-1}C{\hat{P}}_r,\quad Q=-\sqrt{2}BJ_o^{-1}, \\ J_o^TJ_o &=I-{\hat{M}}_0^T{\hat{M}}_0 , \quad J_c J_c^T=I-{\hat{M}}_0 {\hat{M}}_0^T, \quad \Uppi_l={\hat{P}}_l, \quad \Uppi_r={\hat{P}}_r \\ \end{aligned} $$

(3.44)

in the bounded real case. The minimal solution X _min of (3.42) is at least semi-stabilizing in the sense that all the finite eigenvalues of λE − F − EX _min H ^T H are in the closed left half-plane. Such a solution can be computed via the Newton–Kleinman method [10] as presented in Algorithm 6.

Algorithm 6

The generalized Newton–Kleinman method for the projected Riccati equation.

Given E, ${F\in{\mathbb{R}}^{n,n}, H\in{\mathbb{R}}^{m,n},}$ ${Q\in{\mathbb{R}}^{n,m},}$ projectors $\Uppi_r, \Uppi_l$ and a stabilizing initial guess X ₀, compute an approximate solution of the projected Riccati equation (3.42).

FOR $j=1,2,\ldots,$

• 1. Compute $K_j=EX_{j-1}H^T$ and $F_j=F+K_jH.$

• 2. Solve the projected Lyapunov equation

  $$ EX_j F_j^T + F_j X_j E^T=-\Uppi_l (QQ^T-K_j K_j^T)\Uppi_l^T, \quad X_j =\Uppi_r X_j \Uppi_r^T. $$

  END FOR

Similarly to the standard state space case [6, 78], one can show that if λE − F is c-stable, then for X ₀ = 0, all λE − F _j are also c-stable and $\lim\nolimits_{j\to\infty}X_j=X_{\rm min}.$ The convergence is quadratic if the pencil λE − F − EX _min H ^T H is c-stable. Some difficulties may occur if the pencil λE − F has eigenvalues on the imaginary axis. For circuit equations, these eigenvalues are uncontrollable and unobservable [64]. In that case, similarly to [12], one could choose a special stabilizing initial guess X ₀ that ensures the convergence of the Newton–Kleinman iteration. However, the computation of such a guess for large-scale problems remains an open problem.

A low-rank approximation to the minimal solution of the projected Riccati equation (3.42) can be computed in factored form $X_{\min}\approx {\tilde{R}}{\tilde{R}}^T$ with ${\tilde{R}\in{\mathbb{R}}^{n,k}}$, k≪ n using the same approach as in [11]. Starting with $K_1=EX_0H^T$ and $F_1=F+K_1H,$ in each Newton iteration we solve two projected Lyapunov equations

$$ EX_{1,j} F_j^T + F_j X_{1,j} E^T = -\Uppi_l QQ^T\Uppi_l^T, \quad X_{1,j}=P_r X_{1,j} P_r^T, $$

(3.45)

$$ EX_{2,j} F_j^T + F_j X_{2,j}E^T = -\Uppi_l K_j K_j^T\Uppi_l^T, \quad X_{2,j}=\Uppi_l X_{2,j} \Uppi_r^T, $$

(3.46)

for the low-rank approximations $X_{1,j}\approx R_{1,j} R_{1,j}^T$ and $X_{2,j}\approx R_{2,j} R_{2,j}^T,$ respectively, and then compute $K_{j+1}=E(R_{1,j} R_{1,j}^T-R_{2,j} R_{2,j}^T)H^T$ and $F_{j+1}=F+K_{j+1}H.$ If the convergence is observed after j _max iterations, then an approximate solution $X_{\min}\approx{\tilde{R}}{\tilde{R}}^T$ of the projected Riccati equation (3.42) can be computed in factored form by solving the projected Lyapunov equation

$$ EXF^T + FXE^T = -\Uppi_l Q_0 Q_0^T \Uppi_l , \quad X=\Uppi_r X\Uppi_r^T $$

(3.47)

with $Q_0=\left[ Q, E(X_{1,j_{\max}}-X_{2,j_{\max}})H^T\right]$ provided λE − F is c-stable. For computing low-rank factors of the solutions of the projected Lyapunov equations (3.45)–(3.47), we can use the generalized LR-ADI method. Note that in this method we need to compute the products (E + τ F _j )⁻¹ w with ${\tau\in{\mathbb{C}}_-}$ and ${w\in{\mathbb{R}}^n.}$ For example, in the bounded real case we have $E+\tau F_j=E+\tau(A-BC)-\tau {\hat{K}}_jH$ with the low-rank matrices ${H\in{\mathbb{R}}^{m,n}}$ and ${{\hat{K}}_j=\sqrt{2}\hat{P}_lB\hat{M}_0^TJ_c^{-T}-K_j\in{\mathbb{R}}^{n,m}.}$ Then one can use the Sherman–Morrison–Woodbury formula [36, Section 2.1.3] to compute these products as

$$ (E+\tau F_j)^{-1}w= w_1+M_{\hat{K}_j}\left((I_m-HM_{\hat{K}_j})^{-1}Hw_1\right), $$

where w ₁ = (E + τ(A − BC))⁻¹ w and $M_{\hat{K}_j}=\tau(E+\tau(A-BC))^{-1}\hat{K}_j$ can be determined by solving linear systems with the sparse matrix E + τ(A − BC) either by computing sparse LU factorization or by using Krylov subspace methods [68].

5 Numerical Examples

In this section, we present some results of numerical experiments to demonstrate the efficiency of the passivity-preserving balancing-related model reduction methods for circuit equations described in Sect. 3.3 .

Example 3

The first example is a three-port RC circuit provided by NEC Laboratories Europe. The passive reciprocal system of order n = 2007 was approximated by two models of order ℓ = 42 computed by the positive real balanced truncation (PRBT) method and the bounded real balanced truncation (BRBT-M) method applied to the Moebius-transformed system. The minimal solutions of the projected Riccati equations (3.30) and (3.37) were approximated by the low rank matrices $X_{pr}\approx {\tilde{R}}_{pr} {\tilde{R}}_{pr}^T$ with ${{\tilde{R}}_{pr}\in{\mathbb{R}}^{n,123}}$ and $X_{br}\approx{\tilde{R}}_{br} {\tilde{R}}_{br}^T$ with ${{\tilde{R}}_{br}\in{\mathbb{R}}^{n, 125},}$ respectively. Figure 3.3a shows the normalized residuals $\rho(X_j)=\|{\fancyscript{R}}(X_j)\|_F/\|\Uppi_l QQ^T\Uppi_l^T\|_F,$ where $\|\cdot\|_F$ denotes the Frobenius matrix norm, $X_j=R_{1,j} R_{1,j}^T-R_{2,j} R_{2,j}^T$, $\Uppi_l$ and Q are given in (3.43) and (3.44) for (3.30) and (3.37), respectively. Figure 3.3b displays the number of ADI iterations required for solving the projected Lyapunov equations at each Newton iteration.

Fig. 3.3

RC circuit: (a) the convergence history of the low-rank Newton–Kleinman-ADI method; (b) the number of ADI iterations required for solving the projected Lyapunov equations at each Newton iteration

The spectral norms of the frequency responses $\|{{\bf G}}({\rm i}\omega)\|$ and $\|\tilde{{{\bf G}}}({\rm i}\omega)\|$ for a frequency range ω $\in$ [1, 10¹⁵] are presented in Fig. 3.4a. In Fig. 3.4b, we display the absolute errors $\|\widetilde{{{\bf G}}}(i\omega)-{{\bf G}}(i\omega)\|$ for both reduced-order systems and also the error bounds (3.29) and (3.34). As expected, due to the properness of G, the PRBT and BRBT-M methods are equivalent and provide similar results.

Fig. 3.4

RC circuit: (a) the frequency responses of the original and the reduced-order systems; (b) the absolute errors and error bounds

Example 4

The second example is a transmission line model [5] that consists of 20,000 RLC ladders. We approximate the DAE system of order n = 60,000 by a model of order ℓ = 32 computed by the PABTEC method (Algorithm 4). The bounded real Gramian X _br was approximated by a low-rank matrix $X_{br}\approx{\tilde{R}}{\tilde{R}}^T$ with ${{\tilde{R}}\in{\mathbb{R}}^{n,249}}$. Figure 3.5a presents the bounded real characteristic values of the Moebius-transformed system computed as the absolute values of the eigenvalues of ${\tilde{R}}^TS_{\rm int}E{\tilde{R}}.$ One can see that the characteristic values decay rapidly, so we can expect a good approximation by a reduced-order model. The frequency responses of the full-order and the reduced-order models are not presented, since they were impossible to distinguish. Figure 3.5b shows the absolute error $\|\widetilde{{{\bf G}}}(i\omega)-{{\bf G}}(i\omega)\|$ for ω $\in$ [1, 10²⁰] and the error bound (3.34).

Fig. 3.5

Transmission line: (a) the bounded real characteristic values; (b) the absolute error and the error bound (3.34)

6 Conclusions and Open Problems

In this paper, we have discussed balancing-related model reduction methods for linear DAEs arising in circuit simulation. The important property of these methods is the existence of computable error bounds that essentially distinguishes the balanced truncation technique from other model reduction approaches. Moreover, positive real balanced truncation and bounded real balanced truncation applied to a Moebius-transformed system guarantee the preservation of passivity in a reduced-order model that makes these methods very suitable for circuit equations.

Balancing-related model reduction methods for DAEs involve solving projected Lyapunov, Lur’e and Riccati matrix equations. We have presented the efficient numerical algorithms for large-scale projected Lyapunov and Riccati equations based on the LR-ADI iteration and the Newton–Kleinman method, respectively. We have also shown that exploiting the topological structure of circuit equations reduces substantially the numerical complexity of balanced truncation.

Although considerable progress has recently been achieved in developing of balanced truncation methods for large-scale DAEs, some problems still remain open. For example, if $M_0 +M_0^T$ (or $I-{\hat{M}}_0 {\hat{M}}_0^T$) is singular, then to compute the positive real (bounded real) Gramians we have to solve the projected Lur’e equations. Similarly to the standard state space case [82], for small to medium-sized DAE systems, these equations can be transformed to projected Riccati equations of smaller dimension. This approach becomes, however, prohibitive for large-scale problems due to the explicit use of state space transformations. Another problem, already mentioned in Sect. 3.4.2, is the computation of an appropriate stabilizing initial matrix in the Newton–Kleinman iteration in case when the pencil has pure imaginary eigenvalues. This problem could probably be solved for circuit equations by exploiting their special structure.

Finally, in some numerical experiments we observed a very slow convergence of the LR-ADI iteration caused by a poor choice of the shift parameters. The combination of the LR-ADI iteration with the Galerkin projection as proposed in [18, 43] for standard state space systems may improve the performance of the ADI method. Also, a generalization of an extended Krylov subspace method [71] to the projected Lyapunov equations remains for future work.