Model Order Reduction: Methods, Concepts and Properties

Abstract

This chapter offers an introduction to Model Order Reduction (MOR). It gives an overview on the methods that are mostly used. It also describes the main concepts behind the methods and the properties that are aimed to be preserved. The sections are in a prefered order for reading, but can be read independentlty. Section 4.1, written by Michael Striebel, E. Jan W. ter Maten, Kasra Mohaghegh and Roland Pulch, overviews the basic material for MOR and its use in circuit simulation. Issues like Stability, Passivity, Structure preservation, Realizability are discussed. Projection based MOR methods include Krylov-space methods (like PRIMA and SPRIM) and POD-methods. Truncation based MOR includes Balanced Truncation, Poor Man’s TBR and Modal Truncation.Section 4.2, written by Joost Rommes and Nelson Martins, focuses on Modal Truncation. Here eigenvalues are the starting point. The eigenvalue problems related to large-scale dynamical systems are usually too large to be solved completely. The algorithms described in this section are efficient and effective methods for the computation of a few specific dominant eigenvalues of these large-scale systems. It is shown how these algorithms can be used for computing reduced-order models with modal approximation and Krylov-based methods.Section 4.3, written by Maryam Saadvandi and Joost Rommes, concerns passivity preserving model order reduction using the spectral zero method. It detailedly discusses two algorithms, one by Antoulas and one by Sorenson. These two approaches are based on a projection method by selecting spectral zeros of the original transfer function to produce a reduced transfer function that has the specified roots as its spectral zeros. The reduced model preserves passivity.Section 4.4, written by Roxana Ionutiu, Joost Rommes and Athanasios C. Antoulas, refines the spectral zero MOR method to dominant spectral zeros. The new model reduction method for circuit simulation preserves passivity by interpolating dominant spectral zeros. These are computed as poles of an associated Hamiltonian system, using an iterative solver: the subspace accelerated dominant pole algorithm (SADPA). Based on a dominance criterion, SADPA finds relevant spectral zeros and the associated invariant subspaces, which are used to construct the passivity preserving projection. RLC netlist equivalents for the reduced models are provided.Section 4.5, written by Roxana Ionutiu and Joost Rommes, deals with synthesis of a reduced model: reformulate it as a netlist for a circuit. A framework for model reduction and synthesis is presented, which greatly enlarges the options for the re-use of reduced order models in circuit simulation by simulators of choice. Especially when model reduction exploits structure preservation, we show that using the model as a current-driven element is possible, and allows for synthesis without controlled sources. Two synthesis techniques are considered: (1) by means of realizing the reduced transfer function into a netlist and (2) by unstamping the reduced system matrices into a circuit representation. The presented framework serves as a basis for reduction of large parasitic R/RC/RCL networks.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Co-operations Between the Various Co-authors

The subactivity on Model Order Reduction (MOR) of the COMSON project¹ was greatly influenced by interaction with additional research on MOR, first at Philips Research Laboratories and (from october 2006 on) at NXP Semiconductors (both in Eindhoven). There was direct project work with the TU Eindhoven, with the Bergische Universität Wuppertal and with the Royal Institute of Technology (KTH) in Stockholm:

• R. Ionutiu: Model order reduction for multi-terminal Systems – with applications to circuit simulation. Ph.D.-Thesis, TU Eindhoven, 2011, http://alexandria.tue.nl/extra2/716352.pdf.

• M. Saadvandi: Passivity preserving model reduction and selection of spectral zeros. MSc. Thesis, Royal Institute of Technology (KTH), Stockholm. Also published as Technical Note NXP-TN-2008/00276, Unclassified Report, NXP Semiconductors, Eindhoven, 2008. [In September 2012, Maryam Saadvandi did complete a Ph.D.-Thesis at KU Leuven, Belgium, on Nonlinear and parametric model order reduction for second order dynamical systems by the dominant pole algorithm.]

• M.V. Ugryumova: Applications of Model Order Reduction for IC Modeling. Ph.D.-Thesis, TU Eindhoven, 2011, http://alexandria.tue.nl/extra2/711015.pdf.

• A. Verhoeven: Redundancy reduction of IC models by multirate time-integration and model order reduction. Ph.D.-Thesis, TU Eindhoven, 2008,http://alexandria.tue.nl/extra2/200712281.pdf.

• T. Voss: Model reduction for nonlinear differential algebraic equations, MSc. Thesis, University of Wuppertal, 2005. Unclassified Report PR-TN-2005/00919, Philips Research Laboratories, September 2005.[Afterwards, Thomas Voß did complete a Ph.D.-Thesis at the Rijksuniversiteit Groningen, the Netherlands, on Port-Hamiltonian modeling and control of piezoelectric beams and plates: application to inflatable space structures, 2010,http://catalogus.rug.nl/DB=1/SET=1/TTL=4/REL?PPN=326-918639.]

Here Roxana Ionutiu was partially funded by the COMSON project. Apart from TU Eindhoven she also worked with Thanos Antoulas at the Jacobs University in Bremen. Roxana Ionutiu appears several times as co-author in this chapter and in the following ones. Also Maryam Saadvandi appears as co-author of a section. Work by the others is found in the reference lists at each section.

Parallel to the COMSON Project research on MOR was done within the O-MOORE-NICE! project.² The Marie Curie Fellows, Luciano De Tommasi (University of Antwerp), Davit Harutyunyan (TU Eindhoven), Joost Rommes (NXP Semiconductors), and Michael Striebel (Chemnitz University of Technology), interacted actively with the COMSON PhD-students. They contribute to several sections as co-authors, together with researchers from the staff from NXP Semiconductors (Eindhoven), TU Eindhoven, Bergische Universität Wuppertal and the Politehnica Univ. of Bucharest.

The Politehnica Univ. of Bucharest greatly acknowledges co-operation with Jorge Fernandez Villena and Luis Miguel Silveira of INESC-ID in Lisbon. They appear as co-author in the next chapter. Jorge Fernandez Villena was partially funded by the COMSON project. Work in Bucharest and in Lisbon also did benefit from financial support during earlier years from the following complementary projects: FP6/Chameleon, FP5/Codestar, CEEX/nEDA, UEFISCSU/IDEI 609/16.01.2009 and POSDRU/89/1.5/S/62557.

The fourth co-author acknowledges the ENIAC JU Project /2010/SP2(Wireless communication)/270683-2 Artemos, Agile Rf Transceivers and front-Ends for future smart Multi-standard cOmmunications applicationS, http://.artemos.eu.

The COMSON project did directly lead to four Ph.D.-Theses on MOR-related topics:

• Z. Ilievski: Model order reduction and sensitivity analysis. Ph.D.-Thesis, TU Eindhoven, 2010, http://alexandria.tue.nl/extra2/201010770.pdf.

• S. Kula: Reduced order models of interconnects in high frequency integrated circuits. Ph.D.-Thesis, Politehnica Univ. of Bucharest, 2009.

• K. Mohaghegh: Linear and nonlinear model order reduction for numerical simulation of electric circuits. Ph.D.-Thesis, Bergische Universität Wuppertal, Germany. Available at Logos Verlag, Berlin, Germany, 2010.

• A. Ştefănescu: Parametric models for interconnections from analogue high frequency integrated circuits. Ph.D.-Thesis, Politehnica Univ. of Bucharest, 2009.

2 Circuit Simulation and Model Order Reduction

Speaking of “circuit models”, we refer to models of electrical circuits derived by a network approach.³ In circuit simulation the charge-oriented modified nodal analysis (MNA) is a prominent representative of network approaches used to automatically create mathematical models for a physical electrical circuit. In the following we give a short introduction to circuit modeling with MNA. For a detailed discussion we refer to [22].

In charge-oriented MNA, voltages, currents, electrical charges and magnetic fluxes are the quantities that describe the activity of a circuit. The electrical circuit to be modelled is considered to be an aggregation of basic network elements: the ohmic resistor, capacitor, inductor, voltage source and current source. Real physical circuit elements, especially semiconductor devices, are replaced by idealised network elements or so-called “companion models”. The basic network elements correlate the network quantities. Each basic element is associated to a characteristic equations:

• Resistor: I = r(U)  (linear case: $I = \frac{1} {R} \cdot U$)

• Capacitor: $I =\dot{ q}$ with q = q _C (U)  (linear case: $I = C \cdot \dot{ U}$)

• Inductor: $U =\dot{\phi }$ with ϕ = ϕ _L (I)  (linear case: $U = L\cdot\dot{I}$})

• Voltage source: U = v(t)  (controlled source: $U = v(U_{\text{ctrl}},I_{\text{ctrl}},t)$)

• Current source: I = ı(t)  (controlled source: $I = \imath (U_{\text{ctrl}},I_{\text{ctrl}},t)$)

where U is the voltage drop across the element’s terminal, I is the current flowing through the element, q is the electric charge stored in a capacitor and ϕ is the magnetic flux of an inductor. The dot  $\dot{}$  on top of a quantity indicates the usual time derivative d∕dt on that quantity.

All wires, connecting the circuit elements are considered to be electrically ideal, i.e., no wire possesses any resistance, capacitance or inductance. Thereby, also the volume expansion of the circuit becomes irrelevant, the electrical system is considered being a lumped circuit.The circuit’s layout, defined by the interconnects between elements, is thus reduced to its conceptional structure, which is called network topology.

The network’s topology consists of branches and nodes. Each network element is regarded as a branch of the circuit and its terminals are the nodes by which it is connected to other elements. Assigning a direction to each branch – the direction of the current traversing the corresponding element – and a serial number to each node, we end up with a directed graph representing the network. As any directed graph, the network can be described by an incidence matrix A. This matrix has as many columns as there are branches, i.e., elements and as many rows as there are nodes in the circuit. Each column of the matrix has one entry + 1 and one entry − 1, displaying the start and end point of the branch. As all other entries are 0, the matrix A is sparse.

Usually, one circuit node is tagged as ground node. As a consequence, each branch voltage U between two nodes l an m can be expressed by the two node voltages e _l and e _m , which are the voltage differences between each node and the ground node. From this agreement, the node voltage of the ground node is constantly 0 and therefore the information stored in the corresponding row of the incidence matrix becomes redundant and this very row can be removed. Hence, frequently by the term incidence matrix, one refers to the reduced matrix A, given by removing the row corresponding to the ground node.

As each branch of the network represents one of the five basic network element resistor (R), capacitor (C), inductor (L), voltage and current source (V and I, respectively), the indicence matrix can be described as an assembly of element related incidence matrices:

$$\displaystyle\begin{array}{rcl} \mathbf{A} = \left (\mathbf{A}_{C},\mathbf{A}_{R},\mathbf{A}_{L},\mathbf{A}_{V },\mathbf{A}_{I}\right ),& & {}\\ \end{array}$$

with $A_{\varOmega } \in \{ 0,+1,-1\}^{n_{e}\times n_{\varOmega }}$ for Ω ∈ { C, R, L, V, I}. Here, n _e is the number of nodes (without the ground node) and $n_{C},\mathop{\ldots },n_{I}$ are the cardinalities of the sets of the different basic elements’ branches.

The Kirchhoff’s laws, which relate the branch voltages in a loop and the currents accumulating in a node, namely Kirchhoff’s voltage law and Kirchhoff’s current law, respectively, are the final component for setting up the MNA network equations:

$$\displaystyle\begin{array}{rcl} \mathbf{A}_{C} \frac{d} {\mathit{dt}}\mathbf{q} + \mathbf{A}_{R}\mathbf{r}(\mathbf{A}_{R}^{T}\mathbf{e}) + \mathbf{A}_{ L}\boldsymbol{\imath }_{L} + \mathbf{A}_{V }\boldsymbol{\imath }_{V } + \mathbf{A}_{I}\imath (t) = \mathbf{0},& &{}\end{array}$$

(4.1a)

$$\displaystyle\begin{array}{rcl} \frac{d} {\mathit{dt}}\boldsymbol{\phi } -\mathbf{A}_{L}^{T}\mathbf{e} = \mathbf{0},& &{}\end{array}$$

(4.1b)

$$\displaystyle\begin{array}{rcl} \mathbf{v}(t) -\mathbf{A}_{V }^{T}\mathbf{e} = \mathbf{0},& &{}\end{array}$$

(4.1c)

$$\displaystyle\begin{array}{rcl} \mathbf{q} -\mathbf{q}_{C}(\mathbf{A}_{C}^{T}\mathbf{e}) = \mathbf{0},& &{}\end{array}$$

(4.1d)

$$\displaystyle\begin{array}{rcl} \boldsymbol{\phi }-\boldsymbol{\phi }_{L}(\boldsymbol{\imath }_{L}) = \mathbf{0}.& &{}\end{array}$$

(4.1e)

It is worthwile to highlight the subequations (4.1a) and (4.1c). The former is the personification of Kirchhoff’s current law, stating that for each network node the sum of branch currents meeting is identically zero. The latter reflects the functionality of voltage sources: dictating branch voltages.

The unknowns $\mathbf{q},\boldsymbol{\phi },\mathbf{e},\boldsymbol{\imath }_{L},\boldsymbol{\imath }_{V }$, i.e., the charges, fluxes, node voltages and currents traversing inductors and voltage sources, respectively – each of them functions of time t – are combined to the state vector $\mathbf{x}(t) \in \mathbb{R}^{n}$ of unknowns, of dimension $n = n_{C} + n_{L} + n_{e} + n_{L} + n_{V }$. Then, the network equations (4.1) can be stated in a compact form:

$$\displaystyle\begin{array}{rcl} \frac{d} {\mathit{dt}}\mathbf{q}(\mathbf{x}(t)) + \mathbf{j}(\mathbf{x}(t)) + \mathbf{B}\mathbf{u}(t) = \mathbf{0},& &{}\end{array}$$

(4.2)

where $\mathbf{q},\mathbf{j}: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ describe the contribution of reactive and nonreactive elements, respectively.⁴ The excitations defined by the voltage- and current-sources are combined to the vector $\mathbf{u}(t) \in \mathbb{R}^{m}$ with $m = n_{V } + n_{I}$. The excitations are assigned to the corresponding nodes and branches by the matrix $\mathbf{B} \in \mathbb{R}^{n\times m}$.

If the circuit under considerations contains only elements with a linear characteristic equation, the network equations can be written as⁵

$$\displaystyle\begin{array}{rcl} \mathbf{E}\dot{\mathbf{x}}(t) + \mathbf{A}\mathbf{x}(t) + \mathbf{B}\mathbf{u}(t) = \mathbf{0},& &{}\end{array}$$

(4.3a)

with

$$\displaystyle\begin{array}{rcl} \mathbf{E} = \left (\begin{array}{*{10}c} \mathbf{A}_{C}\mathcal{C}\mathbf{A}_{C}^{T}& \mathbf{0} &\mathbf{0} \\ \mathbf{0} &\mathcal{L}&\mathbf{0}\\ \mathbf{0} & \mathbf{0} &\mathbf{0} \end{array} \right ),\quad \mathbf{A} = \left (\begin{array}{*{10}c} \mathbf{A}_{R}\mathcal{G}\mathbf{A}_{R}^{T}&\mathbf{A}_{L}&\mathbf{A}_{V } \\ -\mathbf{A}_{L}^{T} & \mathbf{0} & \mathbf{0} \\ -\mathbf{A}_{V }^{T} & \mathbf{0} & \mathbf{0} \end{array} \right ),\quad \mathbf{B} = \left (\begin{array}{*{10}c} \mathbf{A}_{I}& \mathbf{0} \\ \mathbf{0} & \mathbf{0}\\ \mathbf{0} &\mathbf{I} _{ n_{V }} \end{array} \right ),& &{}\end{array}$$

(4.3b)

where $\mathcal{C},\mathcal{L},\mathcal{G}$ are basically diagonal matrices containing the individual capacitors, inductances and conductances (inverse resistances) of the basic network elements. $\mathbf{I}_{n_{V }}$ is the identity matrix in $\mathbb{R}^{n_{V }\times n_{V }}$.

We arrive at this formulation by eliminating the charges and fluxes. Hence the unknown state vector here is $\mathbf{x} = (\mathbf{e}^{T},\boldsymbol{\imath }_{L}^{T},\boldsymbol{\imath }_{V }^{T})^{T}$ and the excitation vector is $\mathbf{u} = (\boldsymbol{\imath }_{I}^{T},\mathbf{v}^{T})^{T}.$

It is straightforward to see that the structure of the matrices $\mathbf{E},\mathbf{A} \in \mathbb{R}^{n\times n}$ and $\mathbf{B} \in \mathbb{R}^{n\times m}$ is determined by the element related incidence matrices $\mathbf{A}_{C},\mathbf{A}_{R},\mathbf{A}_{L},\mathbf{A}_{V },\mathbf{A}_{I}$. As there is usually only a week linkage amongst the network node, i.e., nodes are connected directly to only a few other nodes, these incidence matrices are sparse and so are the system matrices in (4.3a) and the Jacobian matrices $d\mathbf{q}/d\mathbf{x},d\mathbf{j}/d\mathbf{x} \in \mathbb{R}^{n\times n}$ of the element functions in (4.2), respectively.

In general, real circuit designs contain a large number of transistors. In the course of setting up the network equations such semiconductor devices are replaced by companion models that consist of a larger number of the basic network elements. Here especially resistors with nonlinear characteristics emerge. Hence, the “mathematical image” of an integrated circuit is usually a nonlinear network equation of the form (4.2).

However, also linear network equations of the form (4.3a) are fundamental problems in the design process. As mentioned above, one disregards the volume extension of a circuit and considers wires as electrically ideal. At the end of the design process, however, there will be a physical integrated circuit. Even on the smallest dies there are kilometers of wiring. These wires do have an electric resistance. As the actual devices are getting small and smaller, capacitive effects introduced by neighbouring wires can not be neglected just as little as inductive effects arising from increasing clock rates.

In fact these issues are not neglected. At least at the end of the design process, when the layout of the chip has to be determined these effects are taken into account. In the parasitic extraction from the routing on the chip an artificial linear network is extracted which again is assumed to be a lumped and comprise of ideal wires. However, the resistances, capacitances and inductances that are present there describe the effects caused by the wiring on the actual circuit. A characteristic of these artificial networks is their large dimension: here n can easily be in the range of 10⁶.

The impact of the effects on the behaviour of the actual circuit are accounted for by coupling the linear parasitic model to the underlying circuit design.

If the electrical circuit comprises reactive elements, i.e., capacitors and inductors, the network equation (4.2) or (4.3a), respectively, forms a dynamical problem for the unknown state vector x. Usually, however, the system matrix E, or the Jacobian d q∕d x, respectively, does not have full rank.⁶ Dynamical systems with this property, i.e., systems consisting of differential and algebraic equations are called differential algebraic equations (DAE), or descriptor systems. DAEs differ in several senses from purely differential equations, causing problems in various aspects. A requirement for the solvability of the network equation is the regularity of the matrix pencil {E, A}. The matrix pencil is called regular, if the polynomial det(λ E +A) does not vanish identically. Otherwise {E, A} is called singular matrix pencil. Then a normal initial-value problem for the linear DAE (4.3a) has none or infinitely many solutions. The regularity of the matrix pencil can be checked by examining the element related incidence matrices [15].

In the context of numerical time integration, needed to solve the network problem in time domain, worthwhile stressing that the initial value has to be chosen properly – x(0) has to satisfy the algebraic constraints – and that numerical perturbations can be amplified dramatically. Hence, numerical methods have to match the requirements posed by the differential-algebraic structure.

For a detailed analysis of DAEs we refer to the textbook [29]. A detailed discussion of solving DAEs can be found in the textbook [24].

2.1 Input-Output Systems in Circuit Simulation

We recall that the origin of the network equations in nonlinear or linear form is a real circuit design, ment to be simulated, i.e., tested with respect to its performance under different circumstances. Nowadays, complex integrated circuits are usually not designed from scratch by a single engineer. In fact, large electrical circuits are usually developed in a modular way. In radio frequency applications, for instance, analogue and digital subcircuits are connected to each other. In general several sub-units of different functionality, e.g., one providing stable oscillations another one amplifying a signal, are developed separately and glued together. Hence, subunits possess a way of communication with other subunits, the environment they are embedded in.

To allow for a communication with an environment, the network model (4.2) (or (4.3a)) has to be augmented and transfered to a system that can receive and transmit information. Abstractly, the output of a system can be defined as a function of the state and the input:

$$\displaystyle{ \mathbf{y}(t) = \mathbf{h}(\mathbf{x}(t),\mathbf{u}(t)) \in \mathbb{R}^{p}. }$$

In circuit simulation, however, usually the output is a linear relation of the form:

$$\displaystyle{ \mathbf{y}(t) = \mathbf{C}\mathbf{x}(t) + \mathbf{D}\mathbf{u}(t), }$$

with the output matrix $\mathbf{C} \in \mathbb{R}^{p\times n}$ and the feedthrough matrix $\mathbf{D} \in \mathbb{R}^{p\times m}$.

The excitation, we mentioned above, i.e., the last term Bu(t) in the network model (4.2) (or (4.3a)) can be understood as information imposed on the system, in the form of branch currents and node voltages. Therefore we call u(t) the input and B the input matrix to the system.

Hence, an input-output system in electrical circuit simulation is given in the form

$$\displaystyle\begin{array}{rcl} \mathbf{0} = \mathbf{E}\dot{\mathbf{x}}(t) + \mathbf{A}\mathbf{x}(t) + \mathbf{B}\mathbf{u}(t),& &{}\end{array}$$

(4.4a)

$$\displaystyle\begin{array}{rcl} \mathbf{y}(t) = \mathbf{C}\mathbf{x}(t) + \mathbf{D}\mathbf{u}(t),& &{}\end{array}$$

(4.4b)

if only linear elements form the system. If also nonlinear elements are present, we arrive at systems of the form:

$$\displaystyle\begin{array}{rcl} \mathbf{0} = \frac{d} {\mathit{dt}}\mathbf{q}(\mathbf{x}(t)) + \mathbf{j}(\mathbf{x}(t)) + \mathbf{B}\mathbf{u}(t),& &{}\end{array}$$

(4.5a)

$$\displaystyle\begin{array}{rcl} \mathbf{y}(t) = \mathbf{C}\mathbf{x}(t) + \mathbf{D}\mathbf{u}(t).& &{}\end{array}$$

(4.5b)

The input to state mapping (4.4a) and (4.5a), respectively, is a relation defined by a dynamical system. Therefore, the representation of the input-output system (4.4) and (4.5), respectively, is said to be given in state space formulation. The dimension n of the state space is referred to as the order of the system.

Frequently the state space formulation in circuit design exhibits a special structure.

• Often there is no direct feedthrough of the input to the output, i.e.

  $$\displaystyle{ \mathbf{D} = \mathbf{0} \in \mathbb{R}^{p\times m}. }$$

  (4.6a)

• We often observe

  $$\displaystyle{ p \equiv m\quad \text{and}\quad \mathbf{C} = \mathbf{B}^{T} \in \mathbb{R}^{m\times n}. }$$

  (4.6b)

  In full system simulation, individual subcircuit models are connected to each other. To allow for an information exchange, done in terms of currents and voltages, each subcircuit possesses a set of terminals – a subset of the unit’s pins.

  From a subcircuit’s point of view incoming information is either a current being added to or a voltage drop being imposed to the terminal nodes. The former corresponds to adding a current source term to (4.1a), the latter corresponds to adding a voltage source to (4.1c). Information returned by the subsystem is the voltage at the terminal node in the former case or the current traversing that artificial voltage source in the latter case. Having a detailed look at the MNA network equations (4.1) and the composition of the state vector x(t), it is easy to understand that in this setup, assuming that there are no additional sources in the subcircuits, the output matrix is the transpose of the input matrix.

2.2 The Need for Model Order Reduction

Clearly, mathematical models for a physical circuit are extracted for a purpose. In short, the manufacturing process of an electrical circuit starts with an idea of what the physical system should do and ends with the physical product. In-between there is a, usually iterative, process of conceptual designing the circuit in the form of a circuit schematic, that comprises parameters defining the layout and nominal values of circuit elements and, choosing the parameters, testing the design, adapting the parameter, $\mathop{\ldots }$, etc.

Testing the design means to analyse its behaviour. There are several types of analysis we briefly want to mention in the following. For a more detailed discussion we refer to [22].

• Static (DC) analysis searches for the point to which the system settles in an equilibrium or rest condition. This is characterised by $d/\mathit{dt}\;\mathbf{x}(t) = 0$.

• Transient analysis computes the response y(t) to the time varying excitation u(t) as a function of time.

• (Periodic) steady-state analysis, also called frequency response analysis, determines the response of the system in the frequency domain to an oscillating, i.e., sinusoidal input signal.

• Modal analysis finds the system’s natural vibrating frequency modes and their corresponding modal shapes;

• Sensitivity analysis determines the changes of the time-domain response and/or the frequency-domain response to variations in the design parameters.

Transient analysis is run in the time domain. Here the challenge is to numerically integrate a very high-dimensional DAE problem.

Both the frequency response and the modal analysis are run in the frequency domain. Hence, a network description in the frequency domain is needed. As this is basically defined only for linear systems⁷ we concentrate on linear network problems of the form (4.4). The Laplace transform is the tool to get from the time to the frequency domain.

Recall that for a function $f: [0,\infty ) \rightarrow \mathbb{C}$ with f(0) = 0, the Laplace transform $F: \mathbb{C} \rightarrow \mathbb{C}$ is defined by

$$\displaystyle{ F(s):= \mathcal{L}\{f\}(s) =\int _{ 0}^{\infty }f(t)e^{-st}\mathit{dt}. }$$

For a vector-valued function $\mathbf{f} = (f_{1},\mathop{\ldots },f_{q})^{T}$, the Laplace transform is defined component-wise: $\mathbf{F}(s) = (\mathcal{L}\{f_{1}\}(s),\mathop{\ldots },\mathcal{L}\{f_{q}\}(s))^{T}$.

The physically meaningful values of the complex variable s are s = i ω where ω ≥ 0 is referred to as the (angular) frequency. Taking the Laplace transform of the time domain representation of the linear network problem (4.4) we obtain the following frequency domain representation:

$$\displaystyle\begin{array}{rcl} \mathbf{0}& =& s\mathbf{E}\mathbf{X}(s) + \mathbf{A}\mathbf{X}(s) + \mathbf{B}\mathbf{U}(s), \\ \mathbf{Y}(s)& =& \mathbf{C}\mathbf{X}(s) + \mathbf{D}\mathbf{U}(s), {}\end{array}$$

(4.7)

where X(s), U(s), Y(s) are the Laplace transforms of the states, the input and the output, respectively. Note that we assumed zero initial conditions, i.e., x(0) = 0, u(0) = 0 and y(0) = 0.

Eliminating the variable X(s) in the frequency domain representation (4.7) we see that the system’s response to the input U(s) in the frequency domain is given by

$$\displaystyle\begin{array}{rcl} \mathbf{Y}(s) = \mathbf{H}(s)\mathbf{U}(s)& & {}\\ \end{array}$$

with the matrix-valued transfer function

$$\displaystyle\begin{array}{rcl} \mathbf{H}(s) = -\mathbf{C}\left (s\mathbf{E} + \mathbf{A}\right )^{-1}\mathbf{B} + \mathbf{D}\quad \in \mathbb{C}^{p\times m}.& &{}\end{array}$$

(4.8)

The evaluation of the transfer function is the key to the frequency domain based analyses, i.e., the steady-state analysis and the modal frequency analysis. The key to the evaluation of the transfer function, in turn, is the solution of a linear system with the system Matrix $\left (s\mathbf{E} + \mathbf{A}\right ) \in \mathbb{C}^{n\times n}$.⁸

Note that at the very core of any numerical time integration scheme applied in transient simulation we have to solve as well linear equations with system matrices of the form α E +A were $\alpha \in \mathbb{R}$ depends on some coefficient characteristic to the method and the stepsize used.

It is the order n of the problem, i.e., the dimension of the state space that determines how much computational work has to be spend to compute the p output quantities. Usually, the order n in circuit simulation is very large, whereas the dimension of the output is rather small.

The idea of model order reduction (MOR) is to replace the high dimensional problem by one of reduced order such that the reduced order model produces an output similar to the output of the original problem when excited with the same input.

Before we give an overview of some of the most common MOR techniques we specify the requirement a reduced order model should satisfy. Again, we just briefly describe some concepts. For a more detailed discussion we refer to the textbook [1].

2.2.1 Approximation

The output of the ersatz model should approximate the output of the original model for the same input signal. There are various measures for “being an approximation”. In fact these different viewpoints form the basis for different reduction strategies.

We give first a Theorem (for an ODE) that confirms how an approximation in the frequency domain leads to an accurate result in the time domain. Let $I_{\omega } \subset \mathbb{R}$ be a closed interval (but may be $I_{\omega } =\{\omega _{0}\}$ or $I_{\omega } = \mathbb{R}$). For convenience we assume single input u(t) and single output y(t), with transfer function H(s) in the frequency domain between the Laplace transforms U(s) and Y (s). Let $\tilde{H}(s)$ be the approximation to H(s) which gives $\tilde{Y }(s) =\tilde{ H}(s)\;U(s)$ and $\tilde{y}(t)$ as the output approximation in the time domain.

Theorem 4.1

Let $\vert \vert u(t)\vert \vert _{L^{2}([0,\infty ))} <\infty$ and U(iω) = 0 for $\omega \notin I_{\omega }$ . If the system  (4.4a) consists of ODEs, then we have the estimate

$$\displaystyle{ \max _{t>0}\vert y(t) -\tilde{ y}(t)\vert \leq (\frac{1} {2\pi }\int _{I_{\omega }}\vert H(i\omega ) -\tilde{ H}(i\omega )\vert ^{2}d\omega )^{\frac{1} {2} }(\int _{0}^{\infty }\vert u(t)\vert ^{2}\mathit{dt})^{\frac{1} {2} }. }$$

(4.9)

Proof

We obtain by using the Cauchy-Schwarz inequality in $L^{2}(I_{\omega })$

$$\displaystyle\begin{array}{rcl} \max _{t>0}\vert y(t) -\tilde{ y}(t)\vert & \leq & \max _{t>0}\vert \frac{1} {2\pi }\int _{\mathbb{R}}(Y (i\omega ) -\tilde{ Y }(i\omega ))e^{i\omega t}d\omega \vert {}\\ &\leq & \max _{t>0}\frac{1} {2\pi }\int _{\mathbb{R}}\vert Y (i\omega ) -\tilde{ Y }(i\omega )\vert \cdot \vert e^{i\omega t}\vert \;d\omega {}\\ & =& \frac{1} {2\pi }\int _{\mathbb{R}}\vert H(i\omega ) -\tilde{ H}(i\omega )\vert \cdot \vert U(i\omega )\vert \;d\omega {}\\ & =& \frac{1} {2\pi }\int _{I_{\omega }}\vert H(i\omega ) -\tilde{ H}(i\omega )\vert \cdot \vert U(i\omega )\vert \;d\omega {}\\ & \leq & \frac{1} {2\pi }(\int _{I_{\omega }}\vert H(i\omega ) -\tilde{ H}(i\omega )\vert ^{2}d\omega )^{\frac{1} {2} }(\int _{I_{\omega }}\vert U(i\omega )\vert ^{2}\;d\omega )^{\frac{1} {2} } {}\\ & \leq & (\frac{1} {2\pi }\int _{I_{\omega }}\vert H(i\omega ) -\tilde{ H}(i\omega )\vert ^{2}d\omega )^{\frac{1} {2} }(\int _{0}^{\infty }\vert u(t)\vert ^{2}\mathit{dt})^{\frac{1} {2} }. {}\\ \end{array}$$

This completes the proof. □ 

We note that for $I_{\omega } = \mathbb{R}$ the above error estimate is already found in [23], also for parameterized problems. In [42] the more general case I _ω is considered and applied to Uncertainty Quantification for parameterized problems. In MOR the error estimate becomes often small in an interval I _ω sufficiently close to the used expansion point.

Besides producing similar outputs, the reduced order model should behave similar to the original model in various aspects, which we discuss next.

2.2.2 Stability

One of the principal concepts of analyzing dynamical systems is its stability.

An autonomous dynamical system, i.e., a system without input is called stable if the solution trajectories are bounded in the time domain. For a linear autonomous system the system matrices determine whether it is stable or unstable. Considering for instance the network equation (4.3a) with B ≡ 0 we have to calculate the generalized eigenvalues⁹ $\{\lambda _{i}(\mathbf{A},-\mathbf{E}),i = 1,\mathop{\ldots },n\}$ of the matrix pair (A, −E) to decide whether or not the system is stable. The system is stable if, and only if, all generalized eigenvalues have non-positive real parts and all generalized eigenvalues with $\text{Re}(\lambda _{i}(\mathbf{A},-\mathbf{E})) = 0$ are simple.

2.2.3 Passivity

For input-output systems of the form (4.4), stability is not strong enough. If nonlinear components are connected to a stable system it can become unstable.

For square systems, i.e., system where the number of inputs is equal to the number of outputs, p = m, a property called passivity can be defined. This property is much stronger than stability: it means that a system is unable to generate energy.

Here, an inspection of the system’s transfer function yields evidence if the system is passive or not. A necessary and sufficient conditions for a square system to be passive is that the transfer function is positive real. This means that

• H(s) is analytic for Re(s) > 0;

• $\mathbf{H}(\bar{s}) = \overline{\mathbf{H}(s)}$, for all $s \in \mathbb{C}$;

• The Hermitian part of H(s) is symmetric positive, i.e.: H ^H(s) +H(s) ≥ 0, for all s with Re(s) > 0 [50]. Here^H means the transposed conjugate complex: $\mathbf{A}^{H} =\bar{ \mathbf{A}}^{T}$.

The second condition is satisfied for real systems and the third condition implies the existence of a rational function with a stable inverse. Any congruence transformation applied to the system matrices satisfies the previous conditions if the original system satisfies them, and so preserves passivity of the system if the following conditions are true:

• The system matrices are positive definite, E, A ≥ 0.

• B = C ^T, D = 0.

These conditions are sufficient, but not necessary. They are usually satisfied in the case of electrical circuits, which makes congruence-based projection methods very popular in circuit simulation.

2.2.4 Structure Preservation

For the case of having a circuit made up of linear elements only we have seen in (4.3b) that the system matrices exhibit a block structured form. Furthermore we recognized that the system matrices are sparse. In fact, the same properties hold for the linear case (4.3a) also.

As a consequence, the matrices of the form $\left (\xi \mathbf{E} + \mathbf{A}\right )$ that have to be decomposed during the different modes of analysis exhibit already a form that can be exploited when solving the corresponding linear systems.

If the full system (4.4) is replaced by a small dimensional system, it would be most desirable if that ersatz system again has a structure similar to the structure of the full problem. Namely, a block structure should be preserved and the system matrix arising from the reduced order model should be sparse as well, as it can be more expensive to decompose a small dense matrix then a larger sparse one.

2.2.5 Realizability

Preserving the block structure, as just mentioned, is crucial for realizing a reduced order model again as an RLC-circuit again. Another prerequisit for a reduced order model to be synthesizable is reciprocity.¹⁰ This is a special form of symmetry of the transfer function H. We will not give details here but refer to [44] for a precise definition and MOR techniques and to [6] for other reciprocity preserving MOR techniques.

There is an ongoing discussion if it is necessary to execute this realization (also referred to as un-stamping). It is worthwhile mentioning two benefits of that

• An industrial circuit simulator does in fact never create the MNA equations. Actually, a circuit is given in the form of a netlist, i.e., a table where each line correspond to one element. Each time a system has to be solved, the simulator runs through that list, evaluates each element and stamps the corresponding value in the correct places of the system matrix and the corresponding right-hand side. If a reduced order model is available in the form of such a table as well, the simulator can treat that ersatz model like any other subcircuit and does not have to change to a different mode of including the contribution of the subsystem to the overall system.

• A synthezised reduced order model can provide more insight to the engineers and designers than the reduced order model in mathematical form [52].

2.3 MOR Methods

We recall the idea of model order reduction (MOR):

Replace a high dimensional problem, say of order n by one of reduced order r ≪ n such that the two input-output systems produce a similar output when excited with the same input. Furthermore the reduced order problem should conserve the characteristics of the full model it was derived from.

In fact there is a need for MOR techniques in various fields of applications and for different kind of problem structures. Although a lot of effort is being spent on deriving reliable MOR methods for, e.g., nonlinear problems of the form (4.5) and for linear time varying (LTV) problems – these are problems of the form (4.4) where the system matrices $\mathbf{E},\mathbf{A},\mathop{\ldots }$ depend on time t – MOR approaches for linear time systems, or, more precisely, for linear time invariant (LTI) systems, are best understood and are technically mature.

The outcome of MOR applied to the linear state space problem (4.4) is an ersatz system of the form

$$\displaystyle{ \mathbf{0} =\hat{ \mathbf{E}}\dot{\mathbf{z}}(t) +\hat{ \mathbf{A}}\mathbf{z}(t) +\hat{ \mathbf{B}}\mathbf{u}(t), }$$

(4.10a)

$$\displaystyle{ \tilde{\mathbf{y}}(t) =\hat{ \mathbf{C}}\mathbf{z}(t) +\hat{ \mathbf{D}}\mathbf{u}(t), }$$

(4.10b)

with state variable $\mathbf{z}(t) \in \mathbb{R}^{r}$, output $\tilde{\mathbf{y}}(t) \in \mathbb{R}^{p}$ and system matrices $\hat{\mathbf{E}},\hat{\mathbf{A}} \in \mathbb{R}^{r\times r}$, $\hat{\mathbf{B}} \in \mathbb{R}^{r\times m}$, $\hat{\mathbf{C}} \in \mathbb{R}^{p\times r}$ and $\hat{\mathbf{D}} \in \mathbb{R}^{p\times m}$. The order r of this system is much smaller than the order n of the original system (4.4).

There are many ways to derive such a reduced order model and there are several possibilities for classifying these approaches. It is beyond the scope of this introductory chapter to give a detailed description of all the techniques – for this we refer to [3] and to the textbooks [1, 7, 51] and the papers cited therein.

We classify MOR approaches in projection and truncation based techniques. For each of the two classes we reflect two methods that can be seen as the basis for current developments. Note, that actually it is not possible to draw a sharp line. In fact all MOR techniques aim at keeping major information and removing the less important one. It is in how they measurure importance that the methods differ. In fact several current developments can be regarded as a hybridization of different techniques.

2.4 Projection Based MOR

The concept of all projection based MOR techniques is to approximate the high dimensional state space vector $\mathbf{x}(t) \in \mathbb{R}^{n}$ with the help of a vector $\mathbf{z}(t) \in \mathbb{R}^{r}$ of reduced dimension r ≪ n, within the meaning of

$$\displaystyle{ \mathbf{x}(t) \approx \tilde{\mathbf{x}}(t):= \mathbf{V}\mathbf{z}(t)\quad \mbox{ with $\mathbf{V} \in \mathbb{R}^{n\times r}$}. }$$

Note that the first approximation may be interpreted as a wish. We will only aim for $\mathbf{y}(t) \approx \tilde{\mathbf{y}}(t) = \mathbf{C}\mathbf{V}\mathbf{z}(t) +\hat{ \mathbf{D}}\mathbf{u}(t)$. The columns of the matrix V are a basis of a subspace $\tilde{\mathcal{M}}\subseteq \mathbb{R}^{n}$, i.e., the state space $\mathcal{M}$, the solution x(t) of the network equation (4.4a) resides in, is projected on $\tilde{\mathcal{M}}$. A reduced order model, representing the full problem (4.4) results from deriving a state space equation that determines the reduced state vector z(t) such that $\tilde{\mathbf{x}}(t)$ is a reasonable approximation to x(t).

If we insert $\tilde{\mathbf{x}}(t)$ on the right-hand side of the dynamic part of the input-output problem (4.4a), it will not vanish identically. Instead we get a residual:

$$\displaystyle{ \mathbf{r}(t):= \mathbf{E}\mathbf{V}\dot{\mathbf{z}}(t) + \mathbf{A}\mathbf{V}\mathbf{z}(t) + \mathbf{B}\mathbf{u}(t)\;\; \in \mathbb{R}^{n}. }$$

We can not demand r(t) ≡ 0 in general as this would state an overdetermined system for z(t). Instead we apply the Petrov-Galerkin technique, i.e., we demand the residual to be orthogonal to some testspace $\mathcal{W}$. Assuming that the columns of a matrix $\mathbf{W} \in \mathbb{R}^{n\times r}$ span this testspace, the mathematical formulation of this orthogonality becomes

$$\displaystyle{ \mathbf{0} = \mathbf{W}^{T}\mathbf{r}(t) = \mathbf{W}^{T}\left (\mathbf{E}\mathbf{V}\dot{\mathbf{z}}(t) + \mathbf{A}\mathbf{V}\mathbf{z}(t) + \mathbf{B}\mathbf{u}(t)\right )\;\; \in \mathbb{R}^{r}, }$$

which states a differential equation for the reduced state z(t).

Defining

$$\displaystyle\begin{array}{rcl} \hat{\mathbf{E}}&:=& \mathbf{W}^{T}\mathbf{E}\mathbf{V} \in \mathbb{R}^{r\times r},\ \ \hat{\mathbf{A}}:= \mathbf{W}^{T}\mathbf{A}\mathbf{V} \in \mathbb{R}^{r\times r}, \\ \hat{\mathbf{B}}&:=& \mathbf{W}^{T}\mathbf{B} \in \mathbb{R}^{r\times m},\ \ \hat{\mathbf{C}}:= \mathbf{C}\mathbf{V} \in \mathbb{R}^{p\times r}, \\ \hat{\mathbf{D}}&:=& \mathbf{D} \in \mathbb{R}^{p\times m}, {}\end{array}$$

(4.11)

we arrive at the reduced order model (4.10).

To relate V and W we demand biorthogonality of the spaces $\mathcal{V}$ and $\mathcal{W}$ spanned by the columns of the two matrices, respectively, i.e. $\mathbf{W}^{T}\mathbf{V} = \mathbf{I}_{r}$. With this, the reduced problem (4.10) is the projection of the full problem (4.4) onto $\mathcal{V}$ along $\mathcal{W}$. If an orthonormal V and W = V is chosen, we speak of an orthogonal projection on the space $\mathcal{V}$ (and we come down to a Galerkin method).

Now, MOR projection methods are characterised by the way of how to construct the matrices V and W that define the projection. In the following we find a short introduction of Krylov methods and POD approaches. The former starts from the frequency domain representation, the latter from the time domain formulation of the input-output problem.

2.4.1 Krylov Method

Krylov-based methods to MOR are based on a series expansion of the transfer function H. The idea is to construct a reduced order model such that the series expansions of the transfer function $\hat{\mathbf{H}}$ of the reduced model and the full problem’s transfer function agree up to a certain index of summation.

In the following we will assume that the system under consideration does not have a direct feedthrough, i.e., (4.6a) is satisfied. Furthermore we restrict to SISO systems, i.e., single input single output systems. In this case we have $p = m = 1$, i.e., B = b and C = c ^H where $\mathbf{b},\mathbf{c} \in \mathbb{R}^{n}$, and the (scalar) transfer function becomes:

$$\displaystyle{ \mathbf{H}(s) = -\mathbf{c}^{H}\left (s\mathbf{E} + \mathbf{A}\right )^{-1}\mathbf{b}\;\; \in \mathbb{C}, }$$

As {E, A} is a regular matrix pencil we can find some frequency s ₀ such that s ₀ E +A is regular (for a good discussion on how to choose such “expansion points” s ₀, see [17]). Then the transfer function can be reformulated as

$$\displaystyle{ \mathbf{H}(s) = \mathbf{l}\left (\mathbf{I}_{n} - (s - s_{0})\mathbf{F}\right )^{-1}\mathbf{r}, }$$

(4.12)

with $\mathbf{l}:= -\mathbf{c}^{H}$, $\mathbf{r}:= -(s_{0}\mathbf{E} + \mathbf{A})^{-1}\mathbf{b}$ and $\mathbf{F}:= (s_{0}\mathbf{E} + \mathbf{A})^{-1}\mathbf{A}$.

In a neighbourhood of s ₀ one can replace the matrix inverse in (4.12) by the corresponding Neumann series. Hence, a series expansion of the transfer function is

$$\displaystyle{ \mathbf{H}(s) =\sum _{ k=0}^{\infty }m_{ k}(s - s_{0})^{k}\quad \text{with}\quad m_{ k}:= \mathbf{l}\,\mathbf{F}^{k}\,\mathbf{r}\;\; \in \mathbb{C}. }$$

(4.13)

The quantities m _k for $k = 0,1,\mathop{\ldots }$ are called moments of the transfer function.

A different model, of lower dimension, can now be considered to be an approximation to the full problem, if the moments $\hat{m}_{k}$ of the new model’s transfer function $\hat{\mathbf{H}}(s)$ agree with the moments m _k defined above, for $k = 1,\ldots,q$ for some $q \in \mathbb{N}$.

AWE [38], the Asymptotic Waveform Evaluation, was the first MOR method that was based on this idea. However, the explicit computation of the moments m _k , which is the key to AWE, is numerically unstable. This method can, thus, only be used for small numbers q of moments to be matched.

Expressions like F ^k r or l F ^k arise also in methods, like Krylov-subspace-methods, which are used for the iterative solution of large algebraic equations. Here the Lanczos- and the Arnoldi-method are algorithms that compute biorthogonal bases W, V or a orthonormal basis V of the μth left and/or right Krylov subspaces

$$\displaystyle\begin{array}{rcl} \mathcal{K}_{l}(\mathbf{F}^{T},\mathbf{l}^{T},\mu )&:=& \text{span}\left (\mathbf{l}^{T},\mathbf{F}^{T}\,\mathbf{l}^{T},\mathop{\ldots },\left (\mathbf{F}^{T}\right )^{\mu -1}\,\mathbf{l}^{T}\right ), {}\\ \mathcal{K}_{r}(\mathbf{F},\mathbf{r},\mu )&:=& \text{span}\left (\mathbf{r},\mathbf{F}\,\mathbf{r},\mathop{\ldots },\mathbf{F}^{\mu -1}\,\mathbf{r}\right ), {}\\ \end{array}$$

for $\mu \in \mathbb{N}$, respectively in a numerically robust way.

The Krylov subspaces, thus “contain” the moments m _k of the transfer function and it can be shown, e.g., [2, 12], that from applying Krylov-subspace methods, reduced order models can be created. These reduced order models, however, did not arise from a projection approach. In fact, the Lanczos- and the Arnold-algorithm produces besides the matrices W and/or V whose columns span the Krylov subspaces $\mathcal{K}_{l}$ and/or $\mathcal{K}_{r}$, respectively, a tridiagonal or an upper Hessenbergmatrix $\mathcal{T}$, respectively. This matrix is then used to postulate a dynamical system whose transfer function has the desired matching property.

Concerning the moment matching property there is a difference for reduced order models created from a Lanczos- and those created from an Arnoldi-based process.

For a fixed q, the Lanczos-process constructs the qth left and the qth right Krylov-subspace, hence biorthogonal matrices $\mathbf{W},\mathbf{V} \in \mathbb{R}^{n\times q}$. A reduced order model of order q, arising from this procedure possesses a transfer function $\hat{\mathbf{H}}(s)$ whose first 2q moments coincide with the first 2q moments of the original problem’s transfer function H(s), i.e. $\hat{m}_{k} = m_{k}$ for $k = 0,\mathop{\ldots },2q - 1$. Hence, the Lanczos MOR model yields a Padé approximation.

The Arnoldi method on the other hand is a one sided Krylov subspace method. For a fixed q only the qth right Krylov subspace is constructed. As a consequence, here only the first q moments of the original system’s and the reduced system’s transfer function match.

Owing to their robustness and low computational cost, Krylov subspace algorithms proved suitable for the reduction of large-scale systems, and gained considerable popularity, especially in electrical engineering. A number of Krylov-based MOR algorithms have been developed, including techniques based on the Lanczos method [9, 19] and the Arnoldi algorithm [36, 56]. Note that the moment matching, mentioned above, can only be valid locally, i.e., for a certain frequency range around the expansion point s ₀. However, also Krylov MOR schemes based on a multipoint expansion in the frequency range have been constructed [21].

The main drawbacks of these methods are, in general, lack of provable error bounds for the extracted reduced models, and no guarantee for preserving stability and passivity. There are techniques to turn reduced systems to passive reduced systems. However, this introduced some post-processing of the model [18].

2.4.2 Passivity Preservation

Odabasioglu et al. [36] turned the Krylov based MOR schemes into a real projection method. In addition, the developed scheme, PRIMA (Passive Reduced-Order Interconnect Macromodeling Algorithm), is able to preserve passivity.

This MOR technique can be applied to electrical circuits that contain only passive linear resistors, capacitors and inductors and which accepts only currents as input at the terminals. One says that the RLC-circuit is in impedance form, i.e., the inputs u(t) are currents and the outputs y are voltages.

In this case, the system matrices E, A, B and C have a special structure (cp. (4.3b)), namely:

$$\displaystyle\begin{array}{rcl} \mathbf{E} = \left (\begin{array}{*{10}c} \mathbf{E}_{1} & \mathbf{0} \\ \mathbf{0} &\mathbf{E}_{2} \end{array} \right ),\quad \mathbf{A} = \left (\begin{array}{*{10}c} \mathbf{A}_{1} & \mathbf{A}_{2} \\ -\mathbf{A}_{2}^{T}& \mathbf{0} \end{array} \right ),\quad \mathbf{B} = \mathbf{C}^{T} = \left (\begin{array}{*{10}c} \mathbf{B}_{1} \\ \mathbf{0}\end{array} \right ),& &{}\end{array}$$

(4.14)

where $\mathbf{E}_{1},\mathbf{A}_{1} \in \mathbb{R}^{n_{e}\times n_{e}}$ and $\mathbf{E}_{2} \in \mathbb{R}^{n_{L}\times n_{L}}$ and are symmetric non-negative definit matrices.

In PRIMA, first the Arnoldi method is applied to create the projection matrix V. Then, choosing W = V, the system matrices are reduced according to (4.11). For several implementational details, covering Block-Arnoldi as well as deflation, see [55]. The reduced order model arising in this way can be shown to be passive [36]. The key to these findings is the above special structure of linear RLC-circuits in (4.14).

It is, however, not necessary, to use the Arnoldi method to construct the matrix V. Furthermore, it is also possible to apply the technique to systems in admittance form, i.e., where the inputs are voltages and the outputs are currents. For more details we refer to [27] in this book.

2.4.3 Structure Preservation

As we have seen PRIMA takes advantage of the special block structure (4.14) of linear RLC circuits to create passive reduced order models. The structure, however, is not preserved during the reduction. This makes it hard to synthesise the model, i.e., realize the reduced model as an RLC circuit again.

Freund [12–16] developed a Krylov-based method where passivity, the structure and reciprocity are preserved. SPRIM (Structure-Preserving Reduced-Order Interconnect Macromodell) is similar to PRIMA as first the Arnoldi-method is run to create a matrix $\mathbf{V} \in \mathbb{R}^{n\times r}$. This, however, is not taken as the projection matrix directly. Instead, the matrix V is partitioned to

$$\displaystyle{ \mathbf{V} = \left (\begin{array}{*{10}c} \mathbf{V}_{1} \\ \mathbf{V}_{2} \end{array} \right )\quad \text{with}\quad \mathbf{V}_{1} \in \mathbb{R}^{n_{e}\times r},\mathbf{V}_{ 2} \in \mathbb{R}^{n_{L}\times r}, }$$

corresponding to the block structure of the system matrices E, A, B, C.

Finally, after re-orthogonalization, the blocks $\mathbf{V}_{1},\mathbf{V}_{2}$ are rearranged to the matrix

$$\displaystyle{ \hat{\mathbf{V}} = \left (\begin{array}{*{10}c} \mathbf{V}_{1} & \mathbf{0} \\ \mathbf{0} &\mathbf{V}_{2} \end{array} \right ) \in \mathbb{R}^{n\times (2r)}, }$$

(4.15)

which is then used to transform the system to a reduced order model, according to the transformations given in (4.11) (with $\mathbf{V} = \mathbf{W} =\hat{ \mathbf{V}}$).

It can be shown, that the SPRIM-model preserves twice as many moments as the PRIMA, if the same Arnoldi-method is applied. Note, however, that the dimension also increases by a factor 2.

2.4.4 Multi-input Multi-output

For the general case, where p and m are larger than one, i.e., when we have multiple inputs and multiple outputs, the procedure carried out by the Krylov MOR methods is in principle the same. In this case however, Krylov subspaces for multiple starting vectors have to be computed and one has to take care, when a “breakdown” or a “near-breakdown” occurs, that is, when the basis vectors constructed for differing starting vectors, r ₁ and r ₂ become linearly dependent. In this case the progress for the Krylov subspace becoming linear dependent has to be stopped. The Krylov subspace methods arising from that considerations are called Block Krylov methods. For a detailed discussion we refer to the literature given above.

2.4.5 POD Method

While the Krylov approaches are based on the matrices, i.e., on the system itself, the method of Proper Orthogonal Decomposition (POD) is based on the trajectory x(t), i.e., the outcome of the system (4.4). One could also say that the Krylov methods are based on the frequency domain, whereas POD is based on the time domain formulation of the input output system to be modelled.

POD first collects data $\{\mathbf{x}_{1},\mathop{\ldots },\mathbf{x}_{K}\}$. The datapoints are snapshots of the state space solution x(t) of the network equation (4.4a) at different timepoints t or for different input signals u(t). They are usually constructed by a numerical time simulation, but may also arise from measurements of a real physical system.

From analysing this data, a subspace is created such that the data points as a whole are approximated by corresponding points in the subspace in a optimal least-squares sense. The basis of this approach is also known as Principal Component Analysis and Karhunen–Loève Theorem from picture and data analysis.

The mathematical formulation of POD [39] is as follows: Given a set of K datapoints $X:= \left \{\mathbf{x}_{1},\mathop{\ldots },\mathbf{x}_{K}\right \}$ a subspace $\mathcal{S}_{r} \subset \mathbb{R}^{n}$ of dimension r is searched for that minimizes

$$\displaystyle\begin{array}{rcl} \|X -\varrho _{r}X\|_{2}^{2}:= \frac{1} {K}\sum _{k=1}^{K}\|\mathbf{x}_{ k} -\varrho _{r}\mathbf{x}_{k}\|_{2}^{2},& &{}\end{array}$$

(4.16)

where $\varrho _{r}: \mathbb{R}^{n} \rightarrow \mathcal{S}_{r}$ is the orthogonal projection onto $\mathcal{S}_{r}$.

We will not describe POD in full detail here, as in literature, e.g., [1, 39], this is well explained. However, the key to solving this minimization problem is the computation of the eigenvalues λ _i and eigenvectors $\varphi _{i}$ (for $i = 1,\mathop{\ldots },n$) of the correlation matrix XX ^T:

$$\displaystyle\begin{array}{rcl} \mathbf{X}\mathbf{X}^{T}\boldsymbol{\varphi }_{ i} =\lambda _{i}\boldsymbol{\varphi }_{i},& & {}\\ \end{array}$$

where the eigenvalues and eigenvectors are sorted such that $\lambda _{1} \geq \cdots \geq \lambda _{n}$. The matrix X is defined as $\mathbf{X}:= \left (\mathbf{x}_{1},\mathop{\ldots },\mathbf{x}_{K}\right ) \in \mathbb{R}^{n\times K}$ and is called snapshot matrix.

Intuitively the correlation matrix detects the principal directions in the data cloud that is made up of the snapshots $\mathbf{x}_{1},\mathop{\ldots },\mathbf{x}_{K}$. The eigenvectors and eigenvalues can be thought of as directions and radii of axes of an ellipsoid that incloses the cloud of data. Then, the smaller the radii of one axis is, the less information is lost if that direction is neglected.

The question arises, how many directions r should be kept and how many can be neglected. There is no a-priori error bound for the POD reduction (Rathinam and Petzold [43], though, perform a precise analysis of the POD accuracy). However, the eigenvalues are a measure for the relevance of the dimensions of the state space. Hence, it seems reasonable to choose the dimension r of the reduced order model in such a way, that the relative information content of the reduced model with respect to the full system is high. The measure for this content, used in the literature cited above is

$$\displaystyle{ \mathcal{I}(r) = \frac{\lambda _{1} + \cdots \lambda _{r}} {\lambda _{1} + \cdots \lambda _{r} +\lambda _{r+1} + \cdots \lambda _{n}}. }$$

Clearly, a high relative information content means to have $\mathcal{I}(r) \approx 1$. Typically r is chosen such that this measure is around 0. 99 or 0. 995.

If the eigenvalues and eigenvectors are available and a dimension r has been chosen, the projection matrices V and W in (4.11) are taken as

$$\displaystyle\begin{array}{rcl} \mathbf{V}:= \mathbf{W}:= \left (\boldsymbol{\varphi }_{1},\mathop{\ldots },\boldsymbol{\varphi }_{r}\right ) \in \mathbb{R}^{n\times r}.& & {}\\ \end{array}$$

leading to an orthogonal projection $\varrho _{r} = \mathbf{V}\mathbf{V}^{T}$ on the space $\mathcal{S}_{r}$ spanned by $\varphi _{1},\mathop{\ldots },\varphi _{r}$.

The procedure described so far relies on the eigenvalue decomposition of the n × n matrix XX ^T. This direct approach is feasible only for problems of moderate size. For high dimensional problems, i.e., for dimensions $n \gg 1$, the eigenvalues and eigenvectors are derived form the Singular Value Decomposition (SVD) of the snapshot matrix $\mathbf{X} \in \mathbb{R}^{n\times K}$.

The SVD provides three matrices:

$$\displaystyle\begin{array}{rcl} \boldsymbol{\varPhi }& =& (\varphi _{1},\cdots \,,\varphi _{n}) \in \mathbb{R}^{n\times n}\quad \text{orthogonal,} {}\\ \boldsymbol{\varPsi }& =& (\psi _{1},\cdots \,,\psi _{K}) \in \mathbb{R}^{K\times K}\quad \text{orthogonal,} {}\\ \boldsymbol{\varSigma }& =& \text{diag}\left (\sigma _{1},\mathop{\ldots },\sigma _{\nu }\right ) \in \mathbb{R}^{\nu \times \nu }\quad \mbox{ with $\sigma _{ 1} \geq \cdots \geq \sigma _{\nu }>\sigma _{\nu +1} =\ldots =\sigma _{K} = 0$}, {}\\ \end{array}$$

such that

$$\displaystyle\begin{array}{rcl} \mathbf{X} =\boldsymbol{\varPhi } \left (\begin{array}{*{10}c} \boldsymbol{\varSigma }\, &\,\mathbf{0}\\ \mathbf{0} \, &\,\mathbf{0} \end{array} \right )\boldsymbol{\varPsi }^{T},& &{}\end{array}$$

(4.17)

where the columns of $\boldsymbol{\varPhi }$ and $\boldsymbol{\varPsi }$ are the left and right singular eigenvectors, respectively, and $\sigma _{1},\mathop{\ldots },\sigma _{\nu }$ are the singular values of X (σ _ν being the smallest non-zero singular value; this also defines the index ν). It follows that $\varphi _{1},\mathop{\ldots },\varphi _{n}$ are eigenvectors of the correlation matrix XX ^T with the n eigenvalues $\sigma _{1}^{2},\mathop{\ldots },\sigma _{\nu }^{2},0,\mathop{\ldots },0$.

2.5 Truncation Based MOR

The MOR approaches we reviewed so far rely on the approximation of the high-dimensional state space, the solution of (4.4) resides in, by an appropriate space of lower dimension. An equation for the correspondent z(t) of x(t) is derived by constructing a projection onto that lower-dimensional space.

Although the approaches we are about to describe in the following can also be considered as projection methods in a certain sense, we decided to present them separately. What makes them different, is that these techniques base on preserving key characteristics of the system rather than reproducing the solution. We will get aquainted with an ansatz based upon energy considerations and an approach meant to preserve poles and zeros of the transfer function.

2.5.1 Balanced Truncation

The technique of Balanced Truncation, introduced by Moore [35], is based on control theory, where one essentially investigates how a system can be steered and how its reaction can be observed. In this regard, the basic idea of Balanced Truncation is to first classify, which states x are hard to reach and which states x are hard to deduce from observing the output y, then to reformulate the system such that the two sets of states coincide and finally truncate the system such that the reduced system does not attach importance to these problematic cases.

The system (4.4) can be driven to the state $\bar{\mathbf{x}}$ in time T if an input $\bar{\mathbf{u}}(t)$, with t ∈ [0, T] can be defined such that the solution at time T, i.e., x(T) takes the value $\bar{\mathbf{x}}$ where x(0) = 0. We perceive the L ₂-norm $\|\cdot \|_{2}$, with $\|\bar{\mathbf{u}}\|_{2}^{2} =\int _{ 0}^{T}\bar{\mathbf{u}}(t)^{T}\bar{\mathbf{u}}(t)\;\mathit{dt}$ as energy of the input signal. If the system is in state $\tilde{\mathbf{x}}$ at time t = 0 and no input is applied at its ports we can observe the output $\tilde{\mathbf{y}}(t)$ for t ∈ [0, T] and the energy $\|\tilde{\mathbf{y}}\|_{2}$ emitted at the system’s output ports.

We consider a state as hard to reach if the minimal energy needed to steer the system to that state is large. Similarly, a state whose output energy is small leaves a weak mark and is therefore considered to be hard to be observed.

The minimal input energy needed and the maximal energy emitted can be calculated via the finite and the infinite controllability Gramian

$$\displaystyle\begin{array}{rcl} \boldsymbol{\mathcal{P}}(T) =\int _{ 0}^{T}e^{\mathbf{A}t}\mathbf{B}\mathbf{B}^{T}e^{\mathbf{A}^{T} t}\mathit{dt}\quad \text{and}\quad \boldsymbol{\mathcal{P}} =\int _{ 0}^{\infty }e^{\mathbf{A}t}\mathbf{B}\mathbf{B}^{T}e^{\mathbf{A}^{T} t}\mathit{dt}& &{}\end{array}$$

(4.18a)

and the finite and infinite observability Gramian

$$\displaystyle\begin{array}{rcl} \boldsymbol{\mathcal{Q}}(T) =\int _{ 0}^{T}e^{\mathbf{A}^{T} t}\mathbf{C}^{T}\mathbf{C}e^{\mathbf{A}t}\mathit{dt}\quad \text{and}\quad \boldsymbol{\mathcal{Q}} =\int _{ 0}^{\infty }e^{\mathbf{A}^{T} t}\mathbf{C}^{T}\mathbf{C}e^{\mathbf{A}t}\mathit{dt},& &{}\end{array}$$

(4.18b)

respectively. Note that the system (4.4) is assumed to be stable. Furthermore, the above definition is valid for the case E = I _n×n . The latter does not mean a limitation of the method of Balanced Truncation to standard state space systems. In fact, these considerations can be applied to descriptor systems as well, e.g., [54].

With the above definitions one can prove that the minimal energy needed, i.e., the energy connected to the most economical input $\bar{\mathbf{u}}$, to reach the state $\bar{\mathbf{x}}$ holds

$$\displaystyle\begin{array}{rcl} \|\bar{\mathbf{u}}\|_{2}^{2} =\bar{ \mathbf{x}}^{T}\boldsymbol{\mathcal{P}}^{-1}\bar{\mathbf{x}}.& & {}\\ \end{array}$$

Similarly, the energy emitted due to the state $\tilde{\mathbf{x}}$ holds

$$\displaystyle\begin{array}{rcl} \|\tilde{\mathbf{y}}\|_{2}^{2} =\tilde{ \mathbf{x}}\boldsymbol{\mathcal{Q}}\tilde{\mathbf{x}}.& & {}\\ \end{array}$$

The Gramians are positive definite. Applying a diagonalization of the controllability Gramian, it is easy to see that states that have a large component in the direction of eigenvectors corresponding to small eigenvalues of $\boldsymbol{\mathcal{P}}$ are hard to reach. In the same way it is easy to see that states pointing in the direction of eigenvectors to small eigenvalues of the observability Gramian $\boldsymbol{\mathcal{Q}}$ are hard to observe.

The basic idea of the Balanced Truncation MOR approach is to neglect states that are both hard to reach and hard to observe. This marks the truncation part. However, to reach this synchrony of a state being both hard to reach and hard to observe, the basis of the state space has to be transformed. This marks the balancing part. Generally, a basis transformation introduces new coordinates $\tilde{\mathbf{x}}$ such that $\mathbf{x} = \mathbf{T}^{-1}\tilde{\mathbf{x}}$ where T is the matrix representation of the basis transformation. Here the Gramians transform equivalently to

$$\displaystyle\begin{array}{rcl} \tilde{\boldsymbol{\mathcal{P}}} = \mathbf{T}\boldsymbol{\mathcal{P}}\mathbf{T}^{T}\quad \text{and}\quad \tilde{\boldsymbol{\mathcal{Q}}} = \mathbf{T}^{-1}\boldsymbol{\mathcal{Q}}\mathbf{T}^{-T}.& & {}\\ \end{array}$$

The transformation T is called balancing transformation and the system arising from applying the transformation to the system (4.4) is called balanced if the transformed Gramians satisfy

$$\displaystyle\begin{array}{rcl} \tilde{\boldsymbol{\mathcal{P}}} =\tilde{\boldsymbol{ \mathcal{Q}}} = \text{diag}(\sigma _{1},\mathop{\ldots },\sigma _{n}).& &{}\end{array}$$

(4.19)

The values $\sigma _{1},\mathop{\ldots },\sigma _{n}$ are called Hankel Singular Values. They are the positive square roots of the eigenvalues of the product of the Gramians:

$$\displaystyle\begin{array}{rcl} \sigma _{l} = \sqrt{\lambda _{k } (\boldsymbol{\mathcal{P}} \cdot \boldsymbol{ \mathcal{Q}})},\;\;l = 1,\mathop{\ldots },n.& & {}\\ \end{array}$$

Now we assume that the eigenvalues are sorted in descending order, i.e., $\sigma _{1} \geq \sigma _{2} \geq \cdots \geq \sigma _{n}$. We introduce the cluster

$$\displaystyle\begin{array}{rcl} \left (\begin{array}{ccc|ccc} \sigma _{1} & & & & & \\ & \ddots & & & &\\ & & \sigma _{r } \\ \hline && &\sigma _{r+1}\\ & & & & \ddots\\ & & & & & \sigma _{ n} \end{array} \right ) = \left (\begin{array}{*{10}c} \varSigma _{1}\\ & \varSigma _{ 2} \end{array} \right ),& & {}\\ \end{array}$$

and adopt this to the tranformed input-output system¹¹

$$\displaystyle\begin{array}{rcl} \mathbf{0}& =& \left (\begin{array}{*{10}c} \dot{\tilde{\mathbf{x}}}_{1}(t) \\ \dot{\tilde{\mathbf{x}}}_{2}(t) \end{array} \right ) + \left (\begin{array}{*{10}c} \tilde{\mathbf{A}}_{11} & \tilde{\mathbf{A}}_{12} \\ \tilde{\mathbf{A}}_{21} & \tilde{\mathbf{A}}_{22} \end{array} \right )\left (\begin{array}{*{10}c} \tilde{\mathbf{x}}_{1}(t) \\ \tilde{\mathbf{x}}_{2}(t) \end{array} \right ) + \left (\begin{array}{*{10}c} \tilde{\mathbf{B}}_{1} \\ \tilde{\mathbf{B}}_{2} \end{array} \right )\mathbf{u}(t), \\ \mathbf{y}(t)& =& \left (\mathbf{C}_{1},\mathbf{C}_{2}\right )\left (\begin{array}{*{10}c} \tilde{\mathbf{x}}_{1}(t) \\ \tilde{\mathbf{x}}_{2}(t) \end{array} \right ), {}\end{array}$$

(4.20)

such that $\tilde{\mathbf{x}}_{1} \in \mathbb{R}^{r}$ and $\tilde{\mathbf{x}}_{2} \in \mathbb{R}^{n-r}$.

Finally we separate the cluster and derive the reduced order model

$$\displaystyle\begin{array}{rcl} \mathbf{0} =\dot{\hat{ \mathbf{x}}}_{11}(t) +\tilde{ \mathbf{A}}_{1}\hat{\mathbf{x}}_{1}(t) +\tilde{ \mathbf{B}}_{1}\mathbf{u}(t),& &{}\end{array}$$

(4.21a)

$$\displaystyle\begin{array}{rcl} \tilde{\mathbf{y}}_{1}(t) =\tilde{ \mathbf{C}}_{1}\hat{\mathbf{x}}_{1}(t)& &{}\end{array}$$

(4.21b)

of dimension r ≪ n, by skipping the part corresponding to the small eigenvalues $\sigma _{r+1},\mathop{\ldots },\sigma _{n}$ of both Gramians.

2.5.1.1 Important Properties

Balanced Truncation is an appealing MOR technique because it automatically preserves stability.

Furthermore, and even more attractive is that this MOR approach provides a computable error bound: Let $\sigma _{r+1},\mathop{\ldots },\sigma _{k}$ be the different eigenvalues that are truncated. Then, for the transfer function H ₁ corresponding to (4.21), it holds

$$\displaystyle\begin{array}{rcl} \|\mathbf{H} -\mathbf{H}_{1}\|_{\mathbb{H}_{\infty }} \leq 2\left (\sigma _{r+1} + \cdots +\sigma _{k}\right ),& &{}\end{array}$$

(4.22)

where the $\mathbb{H}_{\infty }$ norm is defined as $\|\mathbf{H}\|_{\mathbb{H}_{\infty }}:=\sup _{\omega \in \mathbb{R}}\|\mathbf{H}(i\omega )\|_{2}$ where $\|\cdot \|_{2}$ is the matrix spectral norm.

2.5.1.2 Computation

Applying the method of Balanced Truncation as presented above makes it necessary to compute the Gramians and the simultaneous diagonalization of the Gramians.

The infinite Gramians $\boldsymbol{\mathcal{P}}$ and $\boldsymbol{\mathcal{Q}}$ are defined by infinity integrals. However, it is not hard to show that they arise from solving the Lyapunov equations:

$$\displaystyle\begin{array}{rcl} \mathbf{A}\boldsymbol{\mathcal{P}} +\boldsymbol{ \mathcal{P}}\mathbf{A}^{T} + \mathbf{B}\mathbf{B}^{T}& =& \mathbf{0} \\ \mathbf{A}^{T}\boldsymbol{\mathcal{Q}} +\boldsymbol{ \mathcal{Q}}\mathbf{A} + \mathbf{C}^{T}\mathbf{C}& =& \mathbf{0}{}\end{array}$$

(4.23)

Having solved the Lyapunov equations, one way to determine the balancing transformation is described by the square root algorithm (see e.g. [1]). The basic steps in this approach are the computation of the Cholesky factorisations of the Gramians $\boldsymbol{\mathcal{P}} = \mathbf{S}^{T}\mathbf{S}$ and $\boldsymbol{\mathcal{Q}} = \mathbf{R}^{T}\mathbf{R}$ and the singular value decomposition of the product SR ^T.

In the past Balanced Bruncation was not favored because the computation of the solution of the high dimensional matrix equations (4.23) and the balancing was very cumbersome and costly. In recent years however, progress was made in the development of techniques to overcome these difficulties. Techniques that can be applied to realize the Balanced Truncation include the ADI method [30], the sign function method [4] or other techniques, e.g. [49]. For a collection of techniques we also refer to [5].

2.5.1.3 Poor Man’s TBR

Another method that should be mentioned is Poor Man’s TBR, ¹² introduced by Phillips and Silveira [37]. Balanced Truncation relies on the Gramians. The methods we mentioned so far compute these Gramians based on the Lyapunov equations (4.23).

The idea of Poor Man’s TBR (PMTBR) however, is to compute the Gramians from their definition (4.18). If the system to be reduced is symmetric, i.e. $\mathbf{A} = \mathbf{A}^{T}$ and C = B ^T, $\boldsymbol{\mathcal{P}}$ and $\boldsymbol{\mathcal{Q}}$ coincide. The (controllability and observability) Gramian is then defined as

$$\displaystyle\begin{array}{rcl} \boldsymbol{\mathcal{P}} =\int _{ 0}^{\infty }e^{\mathbf{A}t}\mathbf{B}\mathbf{B}^{T}e^{\mathbf{A}^{T} t}\mathit{dt}.& & {}\\ \end{array}$$

As the Laplace transform of e ^At is $(s\mathbf{I} -\mathbf{A})^{-1}$, we can apply Parseval’s lemma, which says that a signal’s energy in the time domain is equal to its energy in the frequency domain and transfer the time domain integral to the frequency domain:

$$\displaystyle\begin{array}{rcl} \boldsymbol{\mathcal{P}} =\int _{ -\infty }^{\infty }(i\omega \mathbf{I} -\mathbf{A})^{-1}\mathbf{B}\mathbf{B}^{T}(i\omega \mathbf{I} -\mathbf{A})^{-H}d\omega.& & {}\\ \end{array}$$

PMTBR now starts with applying a numerical quadrature scheme: With nodes ω _k , weights w _k and defining $z_{k} = (i\omega _{k}\mathbf{I} -\mathbf{A})^{-1}\mathbf{B}$ an approximation $\hat{\boldsymbol{\mathcal{P}}}$ to the gramian $\boldsymbol{\mathcal{P}}$ can be computed as:

$$\displaystyle\begin{array}{rcl} \boldsymbol{\mathcal{P}}\approx \hat{\boldsymbol{\mathcal{P}}} =\sum _{k}w_{k}\ z_{k}\ z_{k}^{H} = ZW \cdot (ZW)^{H},& & {}\\ \end{array}$$

where $Z = (z_{1},z_{2},\ldots )$ and $W = \text{diag}(\sqrt{w_{1}},\sqrt{w_{2}},\ldots )$.

For further details on the order reduction we refer to the original paper mentioned above.

2.5.2 Modal Truncation

Engineers usually investigate the transfer behavior of an input-output system by inspecting its frequency response H(i ω) = : G(ω) for frequencies $\omega \in \mathbb{R}^{+}$. The Bode plot, i.e. the combination of the Bode magnitude and phase plot, expressing how much a signal component with a specific frequency is amplified or attenuated and which phase shift can be observed from in- to output, respectively, is a graphical representation of the frequency response.

One is especially interested in the peaks and sinks of the Bode magnitude plot, which are caused by the poles and zeros of the transfer function H. The Modal Truncation [45] is aimed at constructing a reduced order model (4.10) such that peaks and sinks of the reduced order model’s frequency response $\mathbf{\hat{G}}(\omega ) =\hat{ \mathbf{H}}(i\omega )$ match with the one of the full dynamical problem (4.4).

Applying Cramer’s rule it is obvious that the transfer function is a rational function:

$$\displaystyle\begin{array}{rcl} \mathbf{H}(s) = \frac{p_{n-1}(s)} {q_{n}(s)},& & {}\\ \end{array}$$

with polynomials p _n−1 and q _n of degree n − 1 and n respectively. The zeros of the numerator are the zeros of the transfer function and the zeros of the denominator are its poles.

The generalized eigenvalues of the matrix pencil {E, A}, or the eigenvalues of A, if we assume E = I _n×n , are the key to the poles of the transfer function. For a more detailed discussion we refer to [28]. To illustrate this relation we restrict to the latter case and consider a SISO system without direct feedtrough, i.e., D = 0.

The eigentriples $(\lambda _{i},\mathbf{v}_{i},\mathbf{w}_{i})$ for $i = 1,\mathop{\ldots },n$ of A consist of the ith eigenvalue $\lambda _{i} \in \mathbb{C}$ and the ith right and left eigenvalue $\mathbf{v}_{i},\mathbf{w}_{i} \in \mathbb{C}^{n}$, respectively, that satisfy

$$\displaystyle\begin{array}{rcl} \mathbf{A}\mathbf{v}_{i} =\lambda _{i}\mathbf{v}_{i}\quad \text{and}\quad \mathbf{w}_{i}^{H}\mathbf{A} =\lambda _{ i}\mathbf{w}_{i}^{H}.& & {}\\ \end{array}$$

From assuming that A is diagonalizable it can be derived that

$$\displaystyle\begin{array}{rcl} \mathbf{L}^{H}\mathbf{A}\mathbf{R} =\boldsymbol{\varLambda },& & {}\\ \end{array}$$

where $\boldsymbol{\varLambda }= \left (\lambda _{1},\mathop{\ldots },\lambda _{n}\right )$, $\mathbf{R} = \left (\mathbf{v}_{1},\mathop{\ldots },\mathbf{v}_{n}\right )$ and $\mathbf{L} = \left (\mathbf{w}_{1},\mathop{\ldots },\mathbf{w}_{n}\right ) \in \mathbb{C}^{n\times n}$, where the left and right eigenvectors are scaled such that $\mathbf{L}^{H}\mathbf{R} = \mathbf{I}_{n\times n}$.

We apply a change of coordinates $\mathbf{x} = \mathbf{R}\tilde{\mathbf{x}}$ and multiply the input to state mapping (4.4a) with L ^H which is a projection on the space spanned by the columns of R along the space spanned by the columns of L. This transforms the input-output system (4.4) to

$$\displaystyle\begin{array}{rcl} \frac{\text{d}} {\text{d}t}\tilde{\mathbf{x}}& =& \boldsymbol{\varLambda }\tilde{\mathbf{x}} + \mathbf{L}^{H}\mathbf{b}\mathbf{u}, \\ \mathbf{y}& =& \mathbf{c}^{H}\mathbf{R}\tilde{\mathbf{x}}. {}\end{array}$$

(4.24)

The transformed system is equivalent to the original system (4.4), the (scalar) transfer function can be represented as

$$\displaystyle{ \mathbf{H}(s) =\sum _{ i=1}^{n} \frac{r_{i}} {s -\lambda _{i}}\quad \text{with}\quad r_{i} = \left (\mathbf{c}^{H}\mathbf{v}_{ i}\right )\left (\mathbf{w}_{i}^{H}\mathbf{b}\right ) \in \mathbb{C}\quad \mbox{ for $i = 1,\mathop{\ldots },n$}. }$$

(4.25)

This form of displaying the transfer function is known as Pole-Residue Representation, where the quantities $r_{i} \in \mathbb{C}$ are called residues and where we can see that the eigenvalues of the matrix A are the poles of H(s).

The idea of modal truncation is to replace the full order problem with a reduced order model of say order r < n whose transfer function has a pole-residue representation that is a truncation of the corresponding full model’s representation (4.25), i.e.

$$\displaystyle{ \hat{\mathbf{H}}(s) =\sum _{ i=1}^{r} \frac{r_{i}} {s -\lambda _{i}}, }$$

(4.26)

where r _i and λ _i for $i = 1,\mathop{\ldots },r$ are the same as in (4.25). The corresponding state-space representation (4.10) evolves from carrying out the matrix projections defined in (4.11) where $\mathbf{V},\mathbf{W} \in \mathbb{C}^{n\times r}$ comprises r right and left eigenvectors $\mathbf{v}_{1},\mathop{\ldots },\mathbf{v}_{r}$ and $\mathbf{w}_{1},\mathop{\ldots },\mathbf{w}_{r}$, respectively. As no new poles arise by constructing the reduced order model in this way, the stability property is inherited from the full order problem.

Immediately the question arises, which pairs $(\lambda _{i},r_{i})$ of poles and residues and how many should be taken into account.

Rommes [45] and Martins et al. [31] sort these pairs according to decreasing dominance of the pole. Their measure for dominance of a pole is the magnitude of the relation

$$\displaystyle{ \frac{\vert r_{i}\vert } {\vert \text{re}(\lambda _{i})\vert }. }$$

Hence, modal truncation takes into account the first r poles/residues according to this ordering scheme. The answer to the second part of the question, i.e., how many poles/residues to keep, arises from the error bound [20]

$$\displaystyle{ \|\mathbf{H} -\hat{\mathbf{H}}\|_{\mathbb{H}_{\infty }} \leq \sum _{j=r+1}^{n} \frac{\vert r_{j}\vert } {\vert \text{re}(\lambda _{j})\vert }, }$$

(4.27)

and hence from the deviation one is willing to tolerate.

The computation of the error bound (4.27) necessitates a full eigenvalue decomposition. This is only feasible for moderate orders n ≤ 2, 000. For large scale systems methods using only a partial eigenvalue decomposition can be applied. Here the Subspace Accelerated Dominant Pole Algorithm (SADPA), introduced by Rommes and Martins [46] produces a series of dominant poles. The main principle of SADPA is to search for the zeros of $\frac{1} {\mathbf{H}(s)}$ using a Newton-iteration. As the Newton-iteration can only find one zero sufficiently close to a starting value at a time, the iteration procedure has to be applied several times. In order to find less dominant poles at each time, the system the dominant pole algorithm is applied to is adjusted each time one dominant pole has been found. This adjustment is referred to as subspace acceleration.

Again, for further details we refer to the papers cited above.

2.6 Other Approaches

We shortly address some other approaches. In [26, 40, 41], port-Hamiltonian systems are considered to guarantee structure preserving reduced models. In [8, 10, 11], vector fitting techniques are used to obtain passivity preserving reduced models. In [25, 32, 47], one matches additional moments of Laurent expansions involving terms with 1∕s. These are applied to obtain passive reduced models for RLC circuits.

2.7 Examples

In this part we will introduce linear circuits and reduce them with techniques which have already been discussed. We give results for the methods PRIMA [36], SPRIM [12–16], and PMTBR [37].

In simulation a Bode magnitude plot of the transfer function shows the magnitude of $\mathbf{H}(i\omega )$, in decibel, for a number of frequencies ω in the frequency domain of interest. If the transfer function of the original system can be evaluated at enough points s = i ω to produce an accurate Bode plot, the original frequency response can be compared with the frequency response of the reduced model. In our examples, H is a scalar.

2.7.1 Example 1

We choose an RLC ladder network [33] shown in Fig. 4.1. We set all the capacitances and inductances to the same value 1 while $R_{1} = \frac{1} {2}$ and $R_{2} = \frac{1} {5}$, see [34, 53]. We arrange 201 nodes which gives us the order 401 for the mathematical model of the circuit.

Fig. 4.1

RLC Circuit of order $n = 2K - 1$, Example 1

If we write the standard MNA formulation the linear dynamical system is derived. The system matrices are as follows (for K = 3, for example):

$$\displaystyle\begin{array}{rcl} & \mathbf{E} = \mathbf{I},\quad \mathbf{A} = \left [\begin{array}{ccccc} - 2& \;\;0 & \;\;0 &\; - 1&\;\;0\\ \;\;0 & \;\;0 & \;\;0 &\; - 1 &\;\;1 \\ \;\;0 & \;\;0 & - 5& \;\;0 &\;\;1\\ 1 & \;\;1 & \;\;0 & \;\;0 &\;\;0 \\ \;\;0 & - 1&\;\; - 1& \;\;0 &\;\;0 \end{array} \right ],\quad \mathbf{B} = \left [\begin{array}{c} 0\\ 0 \\ 5\\ 0 \\ 0 \end{array} \right ],& \\ & \mathbf{C} = \left [\begin{array}{ccccc} 0&0& - 5&0&0 \end{array} \right ],\quad D = 5. &{}\end{array}$$

(4.28)

In the state variable x, x _k is the voltage across capacitance C _k (k = 1, …, K), or the current through inductor L _k−K ($k = K + 1,\ldots,2K - 1$). In general the number of nodes K is odd. The voltage u and the current y are input and output, respectively. Note that when the number of nodes is K the order of the system becomes $n = 2K - 1$. In this test case we have an ODE instead of a DAE as E = I, see (4.28). The original transfer function is shown in Fig. 4.2. The plot already illustrates how difficult it is to reduce this transfer function as many oscillations appear.

Fig. 4.2

Original transfer function for the first example of Fig. 4.1, order n = 401. The frequency domain parameter ω varies between 10⁻² to 10³

2.7.2 Example 2

Next, we use another RLC ladder network, given in Fig. 4.3 [33, 48], for the second example.

Fig. 4.3

RLC Circuit of order $n = 2K - 1$, Example 2

The major difference to the previous example is that we introduced a resistor (all of equal value) in parallel to the capacitors at each node connected to the ground. We set all the capacitances and inductances to the same value 1 while $R_{1} = \frac{1} {2}$, $R_{2} = \frac{1} {5}$ and R = 1. We choose 201 nodes which results in a system having order 401 for the mathematical model of the circuit. Like the previous example we again derive a system of ODEs. The original transfer function of the second example is shown in Fig. 4.4.

Fig. 4.4

Original transfer function for the second example of Fig. 4.3, order n = 401. The frequency domain parameter ω varies between 10⁻² to 10³

2.7.3 MOR by PRIMA, SPRIM and PMTBR

The main reason for choosing these two examples is the behavior of the Hankel singular values, see Fig. 4.5. The Hankel singular values for the first example do not show any significant decay, while in the second example we observe a rapid decay in the values. The results are taken from [33].

Fig. 4.5

Hankel Singular Values for Example 1 and 2, (semi-logarithmic scale)

The Figs. 4.6 and 4.7 show the absolute error between the transfer function of the full system and the transfer function of several reduced systems. The model is reduced by three linear techniques (PRIMA, SPRIM and PMTBR) for both examples.

Fig. 4.6

Error plot, the frequency domain parameter ω varies between 10⁻² to 10³, Example 1

Fig. 4.7

Error plot, the frequency domain parameter ω varies between 10⁻² to 10³, Example 2

In the Example 1 we reduced the system from order n = 401 (number of nodes is K = 201) to order 34, which means that we reduced the system (in all three methods) by a factor of 10. The order of the reduced model is relatively large in this case as the dynamical system is somehow stubborn for any reductions, see Fig. 4.5. The price we will pay for a smaller system is too high as we loose a lot of information during the reduction and the error is becoming relatively large. As we expected, PRIMA and SPRIM in Fig. 4.6 produced reliable results close to the expansion point, in this case s = 0, but the error is immediately increasing for the rest of the oscillation part, see Fig. 4.2, and then smoothly decreases for higher frequencies. In the first example the PMTBR method matches a bit worse for the low frequencies as the error decreases just for a short interval and immediately starts to increase again. But PMTBR also cannot cover the oscillation part of the transfer function although it resolves the higher frequencies well. The order in PMTBR results from a prescribed tolerance.

For the second example the SPRIM and PRIMA produced a nice match around the expansion point, s = 0, like the first example, but for a larger interval, see Fig. 4.7. The peaks of error for both PRIMA and SPRIM are around − 50 and − 80 dB, respectively, which are much lower than in Example 1 where the peaks are around 0 dB for both PRIMA and SPRIM. We allowed PMTBR to reduce the system by a factor of 20 in this case although we keep the order of the reduced system the same as for the first example for the PRIMA and SPRIM. Despite the lower dimension for the reduced system PMTBR produced much better results for this test case compared to the first example as the error starts from − 50 dB and smoothly decreases for low frequencies and suddenly falls to − 300 dB for larger frequencies.

As we expected, the SPRIM produces a better approximation than PRIMA, especially for the second example, since it matches twice as much moments. Although both methods have a good agreement around the expansion point s = 0, the error increases as we are far from the expansion point. Since the Hankel singular values for the first example do not decay, the PMTBR method cannot produce an accurate model for low frequencies in that case. In the second example where the Hankel singular values rapidly decay PMTBR produced a more reliable result with a better match. This shows that we cannot stick to one method for reduction in general and the method should be chosen depending on the circuit’s behavior.

2.8 Summary

In industrial applications of different disciplines, model order reduction is gaining more and more interest. As there is not the one and only type of model to describe all kinds of dynamics of different physical problems there is not and will never be the one and only MOR technique that fits best to all problems. Hence, research on MOR techniques is an ongoing process.

In the following contributions in this chapter you will find different approaches to different questions, aiming to attack different facets of reduced order models. This introductory contribution was ment to give an overview of the basic ideas and the motivation of some MOR techniques that are applied and refined throughout this chapter.

3 Eigenvalue Methods and Model Order Reduction

Physical structures and processes are modeled by dynamical systems in a wide range of application areas.¹³ The increasing demand for complex components and large structures, together with an increasing demand for detail and accuracy, makes the models larger and more complicated. To be able to simulate these large-scale systems, there is need for reduced-order models of much smaller size, that approximate the behavior of the original model and preserve the important characteristics.

In order to preserve the important characteristics, one usually first has to know what are the important characteristics. For linear dynamical systems, two important characteristics are the dominant dynamics and stability. The dominant dynamics are determined by the dominant modes of the system, while stability of the system is determined by the location of the eigenvalues. Hence, both characteristics can be computed by solving eigenvalue problems: the dominant dynamics can be found by computing the dominant eigenvalues (poles) and corresponding eigenvectors, while stability can be assessed by determining whether the system has no eigenvalues in the right half-plane (the system is stable if there are no eigenvalues with real part greater than zero).

A large-scale dynamical system can have a large number of modes. Like a general square matrix can be approximated by its largest eigenvalues, i.e. by projecting it onto the space spanned by the eigenvectors corresponding to the largest eigenvalues, a dynamical system can be approximated by its dominant modes: a reduced order model, called the modal equivalent, can be obtained by projecting the state space on the subspace spanned by the dominant eigenvectors. This technique, modal approximation or modal model reduction, has been successfully applied to scalar and multivariable transfer functions of large-scale power systems, with applications such as stability analysis and controller design, see [81, 82].

The dominant eigenvectors, and the corresponding dominant poles of the system transfer function, are specific eigenvectors and eigenvalues of the state matrix. Because the systems are very large in practice, it is not feasible to compute all eigenvectors and to select the dominant ones.

Section 4.2 is concerned with the efficient computation of the dominant poles and eigenvectors specifically, and their use in model order reduction. The section is organized as follows. In Sect. 4.2.1 the concept of dominant poles and modal approximation is explained in more detail. Dominant poles can be computed with specialized eigensolution methods, as is described in Sect. 4.2.2. Some generalizations of the presented algorithms are shown in Sect. 4.2.3. Ideas on how to improve Krylov based MOR methods by using dominant poles are discussed in Sect. 4.2.4. Numerical examples are presented in Sect. 4.2.5. Section 4.2.6 concludes.

For general introductions to model order reduction we refer to the previous Sect. 4.1 and to [58, 60, 61, 88]; for eigenvalue problems, see [87, 93]. More detailed publications on the contents of this section are [80–85]. The pseudocode algorithms presented in this section are written using Matlab-like [92] notation.

3.1 Transfer Functions, Dominant Poles and Modal Equivalents

In Sect. 4.2, the dynamical systems (E, A, b, c, d) are of the form

$$\displaystyle{ \left \{\begin{array}{lll} E\dot{\mathbf{x}}(t)& =&A\mathbf{x}(t) + \mathbf{b}u(t)\\ y(t) & = &\mathbf{c} ^{{\ast} } \mathbf{x} (t) + du(t), \end{array} \right. }$$

(4.29)

where $A,E \in \mathbb{R}^{n\times n}$, E may be singular, $\mathbf{b},\mathbf{c},\mathbf{x}(t) \in \mathbb{R}^{n}$, $u(t),y(t),d \in \mathbb{R}$. The vectors b and c are called the input, and output map, respectively. The transfer function $H: \mathbb{C} \rightarrow \mathbb{C}$ of (4.29) is defined as

$$\displaystyle{ H(s) = \mathbf{c}^{{\ast}}(\mathit{sE} - A)^{-1}\mathbf{b} + d. }$$

(4.30)

The poles of the transfer function in (4.30) are a subset of the eigenvalues $\lambda _{i} \in \mathbb{C}$ of the matrix pencil (A, E). An eigentriplet $(\lambda _{i},\mathbf{x}_{i},\mathbf{y}_{i})$ is composed of an eigenvalue λ _i of (A, E) and corresponding right and left eigenvectors $\mathbf{x}_{i},\mathbf{y}_{i} \in \mathbb{C}^{n}$:

$$\displaystyle\begin{array}{rcl} A\mathbf{x}_{i}& =& \lambda _{i}E\mathbf{x}_{i},\qquad \mathbf{x}_{i}\neq 0, {}\\ \mathbf{y}_{i}^{{\ast}}A& =& \lambda _{ i}\mathbf{y}_{i}^{{\ast}}E,\qquad \mathbf{y}_{ i}\neq 0,\qquad (i = 1,\ldots,n). {}\\ \end{array}$$

The actual occurring poles in (4.30) are identified by the components of the eigenvectors in in b and c. Assuming that the pencil is nondefective, the right and left eigenvectors corresponding to the same finite eigenvalue can be scaled so that $\mathbf{y}_{i}^{{\ast}}E\mathbf{x}_{i} = 1$. Furthermore, it is well known that left and right eigenvectors corresponding to distinct eigenvalues are E-orthogonal: $\mathbf{y}_{i}^{{\ast}}E\mathbf{x}_{j} = 0$ for i ≠ j. The transfer function H(s) can be expressed as a sum of residues $R_{i} \in \mathbb{C}$ over the $\tilde{n} \leq n$ finite first order poles [68]:

$$\displaystyle{ H(s) =\sum _{ i=1}^{\tilde{n}} \frac{R_{i}} {s -\lambda _{i}} + R_{\infty } + d, }$$

(4.31)

where the residues R _i are

$$\displaystyle{ R_{i} = (\mathbf{c}^{{\ast}}\mathbf{x}_{ i})(\mathbf{y}_{i}^{{\ast}}\mathbf{b}), }$$

and R _∞ is the constant contribution of the poles at infinity (often zero).

Although there are different indices of modal dominance [57, 64, 94], the following will be used in this chapter.

Definition 4.1

A pole λ _i of H(s) with corresponding right and left eigenvectors x _i and y _i ($\mathbf{y}_{i}^{{\ast}}E\mathbf{x}_{i} = 1$) is called the dominant pole if $\vert R_{i}\vert /\vert \mbox{ Re}(\lambda _{i})\vert> \vert R_{j}\vert /\vert \mbox{ Re}(\lambda _{j})\vert$, for all j ≠ i.

More generally, a pole λ _i is called dominant if $\vert R_{i}\vert /\vert \mbox{ Re}(\lambda _{i})\vert$ is not small compared to $\vert R_{j}\vert /\vert \mbox{ Re}(\lambda _{j})\vert$, for all j ≠ i. A dominant pole is well observable and controllable in the transfer function. This can also be seen in the corresponding Bode-plot, which is a plot of the magnitude | H(i ω) | against $\omega \in \mathbb{R}$: peaks occur at frequencies ω close to the imaginary parts of the dominant poles of H(s). In practise one also plots the corresponding phase of H(i ω). An approximation of H(s) that consists of k < n terms with $\vert R_{j}\vert /\vert \mbox{ Re}(\lambda _{j})\vert$ above some value, determines the effective transfer function behavior [90] and is also known as transfer function modal equivalent:

Definition 4.2

A transfer function modal equivalent H _k (s) is an approximation of a transfer function H(s) that consists of k < n terms:

$$\displaystyle{ H_{k}(s) =\sum _{ j=1}^{k} \frac{R_{j}} {s -\lambda _{j}} + d. }$$

(4.32)

A modal equivalent that consists of the most dominant terms determines the effective transfer function behavior [90]. If $X \in \mathbb{C}^{n\times k}$ and $Y \in \mathbb{C}^{n\times k}$ are matrices having the left and right eigenvectors y _i and x _i of (A, E) as columns, such that $Y ^{{\ast}}\mathit{AX} =\varLambda = \mbox{ diag}(\lambda _{1},\ldots,\lambda _{k})$, with Y ^∗ EX = I, then the corresponding (complex) reduced system follows by setting $\mathbf{x} = X\tilde{\mathbf{x}}$ and multiplying from the left by Y ^∗:

$$\displaystyle{ \left \{\begin{array}{lll} \dot{\tilde{\mathbf{x}}}(t)& =&\varLambda \tilde{\mathbf{x}}(t) + (Y ^{{\ast}}\mathbf{b})u(t) \\ \tilde{y}(t) & =&(\mathbf{c}^{{\ast}}X)\tilde{\mathbf{x}}(t) + \mathit{du}(t).\end{array} \right. }$$

In practice, it is advisable to make a real reduced model in the following way: for every complex pole triplet (λ, x, y), construct real bases for the right and left eigenspace via [Re(x), Im(x)] and [Re(y), Im(y)], respectively. Let the columns of X _r and Y _r be such bases, respectively. Because the complex conjugate eigenvectors are also in this space, the real bases for the eigenspaces are still (at most) k dimensional. The real reduced model can be formed by using X _r and Y _r in $(Y _{r}^{{\ast}}\mathit{EX}_{r},Y _{r}^{{\ast}}\mathit{AX}_{r},Y _{r}^{{\ast}}\mathbf{b},X_{r}^{{\ast}}\mathbf{c},d)$.

For stable nondefective systems, the error in the modal equivalent can be quantified as [64]

$$\displaystyle\begin{array}{rcl} \|H - H_{k}\|_{\infty }& =& \|\sum _{j=k+1}^{n} \frac{R_{j}} {s -\lambda _{j}}\|_{\infty } {}\\ &\leq & \sum _{j=k+1}^{n} \frac{\vert R_{j}\vert } {\vert \mbox{ Re}(\lambda _{j})\vert }, {}\\ & & {}\\ \end{array}$$

where $\|H\|_{\infty }$ is the operator norm induced by the 2-norm in the frequency domain [58, 64]. An advantage of modal approximation is that the poles of the modal equivalent are also poles of the original system.

The dominant poles are specific (complex) eigenvalues of the pencil (A, E) and usually form a small subset of the spectrum of (A, E), so that rather accurate modal equivalents may be possible for k ≪ n. Since the dominant poles can be located anywhere in the spectrum, specialized eigensolution methods are needed. Because the dominance of a pole is independent of d, without loss of generality d = 0 in the following.

3.2 Specialized Eigensolution Methods

In this section we describe the Dominant Pole Algorithm and its extension with deflation and subspace acceleration.

3.2.1 The Dominant Pole Algorithm (DPA)

The poles of the transfer function (4.30) are the $\lambda \in \mathbb{C}$ for which $\lim _{s\rightarrow \lambda }\vert H(s)\vert = \infty$ and can be computed via the roots of $G(s) = 1/H(s)$. Applying Newton’s method leads to the scheme

$$\displaystyle\begin{array}{rcl} s_{k+1}& =& s_{k} - \frac{\mathbf{c}^{{\ast}}\mathbf{v}_{k}} {\mathbf{w}_{k}^{{\ast}}E\mathbf{v}_{k}},{}\end{array}$$

(4.33)

where $\mathbf{v}_{k} = (s_{k}E - A)^{-1}\mathbf{b}$ and $\mathbf{w}_{k} = (s_{k}E - A)^{-{\ast}}\mathbf{c}$. The algorithm based on this scheme, also known as the Dominant Pole Algorithm (DPA) [72], is shown in Algorithm 4.1. Note that strictly speaking the definition of dominance used here is based on | R _j  | (and not on $\vert R_{j}\vert /\vert \mbox{ Re}(\lambda _{j})\vert$ as in Definition 4.1); observe that in (4.32) $R_{j} = (\mathbf{c}^{{\ast}}\mathbf{x}_{j})(\mathbf{y}_{j}^{{\ast}}\mathbf{b})$. The subsequent algorithms offer refinements that may lead to additional candidates, in any user-specified dominance criterion, including Definition 4.1.

Algorithm 4.1 The Dominant Pole Algorithm (DPA)

The Dominant Pole Algorithm is closely related to Rayleigh Quotient Iteration [76, 77]: the only difference is that in DPA the right hand-sides in Step 3 and 4 remain fixed, while in Rayleigh Quotient Iterations these are updated with $\mathbf{b} = E\mathbf{v}_{k-1}$ and $\mathbf{c} = E^{{\ast}}\mathbf{w}_{k-1}$ every iteration. See [85] for a detailed comparison.

The two linear systems that need to be solved in step 3 and 4 of Algorithm 4.1 to compute the Newton update in (4.33) can be efficiently solved using one LU-factorization $\mathit{LU} = s_{k}E - A$, by noting that $U^{{\ast}}L^{{\ast}} = (s_{k}E - A)^{{\ast}}$. If an exact LU-factorization is not available, one has to use inexact Newton schemes, such as inexact Rayleigh Quotient Iteration and Jacobi-Davidson style methods [67, 89, 91]. In the next section, extensions of DPA are presented that are able to compute more than one eigenvalue in an effective and efficient way.

3.2.2 Deflation and Subspace Acceleration

In practical applications often more than one dominant pole is wanted: one is interested in all the dominant poles, no matter what definition of dominance is used. Simply running the single pole algorithm DPA for a number of different initial shifts will most likely result in duplicate dominant poles. A well known strategy to avoid computation of already found eigenvalues is deflation, see for instance [87]. It is also known that subspace acceleration may improve the global convergence: for an n × n problem, the subspace accelerated algorithm converges within at most n iterations, although in practice it may need only k ≪ n iterations and will almost never build a full search space of dimension n, but restart every k _max  ≪ n iterations. The use of subspace acceleration requires that every iteration an approximate pole has to be selected from the available approximations. This also may improve the global convergence, since better approximations than the initial estimate, which may be a rather crude approximation, become available during the process.

In the next subsections, variants of DPA for the computation of more than one pole without and with subspace acceleration are discussed. This variant that does not use subspace acceleration can be implemented efficiently with only constant costs for deflation, while the subspace accelerated variant has better global convergence.

Throughout the rest of this chapter, let the (n × k) matrices X _k and Y _k have as their columns the normalized (found) right and left eigenvectors x _i and y _i (i = 1, …, k) of (A, E), respectively, and let Λ _k be a diagonal (k × k) matrix with the corresponding eigenvalues on its diagonal, i.e. $\varLambda _{k} = \mbox{ diag}(\lambda _{1},\ldots,\lambda _{k})$, $Y _{k}^{{\ast}}\mathit{AX}_{k} =\varLambda _{k}$ and $Y _{k}^{{\ast}}\mathit{EX}_{k} = I$. For ease of notation, the subscript k will be omitted if this does not lead to confusion.

3.2.3 DPA with Deflation by Restriction

It can be verified that if X ≡ X _k and Y ≡ Y _k have as their columns exact eigenvectors (normalized so that Y ^∗ EX = I), then the system $(E_{d},A_{d},\mathbf{b}_{d},\mathbf{c}_{d})$, where

$$\displaystyle\begin{array}{rcl} E_{d}& =& (I -\mathit{EXY }^{{\ast}})E(I -\mathit{XY }^{{\ast}}E), {}\\ A_{d}& =& (I -\mathit{EXY }^{{\ast}})A(I -\mathit{XY }^{{\ast}}E), {}\\ \mathbf{b}_{d}& =& (I -\mathit{EXY }^{{\ast}})\mathbf{b}, {}\\ \mathbf{c}_{d}& =& (I - E^{{\ast}}\mathit{YX}^{{\ast}})\mathbf{c}, {}\\ \end{array}$$

has the same poles, eigenvectors and residues, but with the found λ _i (i = 1, …, k) and corresponding R _i transformed to 0. So in order to avoid recomputing the same pole, DPA could be applied to the deflated system $(E_{d},A_{d},\mathbf{b}_{d},\mathbf{c}_{d})$ after having found one or more poles. This would require solves with $(\mathit{sE}_{d} - A_{d})$ and $(\mathit{sE}_{d} - A_{d})^{{\ast}}$ in step 4 and 5 of Algorithm 4.2,¹⁴ but the following theorem shows that it is sufficient to only replace b by b _d and c by c _d to ensure deflation.

Theorem 4.2 ([80, Thm. 3.3.1])

The deflated transfer function $H_{d}(s) = \mathbf{c}_{d}^{{\ast}}(\mathit{sE} - A)^{-1}\mathbf{b}_{d}$ , where

$$\displaystyle\begin{array}{rcl} \mathbf{b}_{d} = (I -\mathit{EXY }^{{\ast}})\mathbf{b}& \mbox{ and }& \mathbf{c}_{ d} = (I - E^{{\ast}}\mathit{YX}^{{\ast}})\mathbf{c}, {}\\ \end{array}$$

has the same poles λ _i and corresponding residues R _i as $H(s) = \mathbf{c}^{{\ast}}(\mathit{sE} - A)^{-1}\mathbf{b}$ , but with the residues R _i corresponding to the found poles λ _i (i = 1,…,k) transformed to R _i = 0.

Proof

The proof follows by using the definition of residues and basic linear algebra [80, Thm. 3.3.1]. □ 

Algorithm 4.2 Dominant Pole Algorithm with deflation (DPAd)

Fig. 4.8

Exact transfer function (solid) of the New England test system [72], and modal equivalents where the following dominant pole (pairs) are removed one by one: − 0. 467 ± 8. 96i (square), − 0. 297 ± 6. 96i (asterisk), − 0. 0649 (diamond), and − 0. 249 ± 3. 69i (circle). Note that the corresponding peaks are removed from the Bode plot as well (to see this, check the Bode plot at the frequencies near the imaginary part of the removed pole)

In other words, by using b _d and c _d the found dominant poles are degraded to non dominant poles of H _d (s), while not changing the dominance of the remaining poles. Hence these poles will not be recomputed by DPA applied to H _d (s). Graphically, the peaks caused by the found poles are ’flattened’ in the Bode plot (see also Fig. 4.8).

Note that if $H(s) = \mathbf{c}^{{\ast}}(\mathit{sE} - A)^{-1}\mathbf{b} + d$ with d = 0, then the deflated poles in fact become zeros of H _d (s). It can be shown that DPA applied to $H_{d}(s) = \mathbf{c}_{d}^{{\ast}}(\mathit{sE} - A)^{-1}\mathbf{b}_{d}$ and DPA applied to $H_{\tilde{d}}(s) = \mathbf{c}_{d}^{{\ast}}(\mathit{sE}_{d} - A_{d})^{-1}\mathbf{b}_{d}$ produce the same results [85].

The important result is that the single pole DPA can easily be extended, see Algorithm 4.2, to an algorithm that is able to compute more than one pole, while maintaining constant costs per iteration, except for iterations in which a pole is found. The only change to be made to Algorithm 4.1, is when a dominant pole triplet (λ, x, y) is found: in that case, the algorithm continues with b and c replaced by (I − E xy ^∗)b and $(I - E^{{\ast}}\mathbf{y}\mathbf{x}^{{\ast}})\mathbf{c}$, respectively.

This approach has a number of advantages. The implementation is straightforward and efficient: search spaces, selection strategies and orthogonalization procedures are not needed, so that the computational costs per iteration remain constant, even if the number of found poles increases. For every found pole only two skew projections are needed once to compute the new b _d and c _d , so the costs for deflation are constant. The pseudo code in Algorithm 4.2 can almost literally be used as Matlab code. The special properties of DPA ensure convergence to dominant poles (locally). Furthermore, the deflation of found poles is numerically stable in the sense that even if the corresponding transformed residues are not exactly zero, which is usually the case in finite arithmetic, this will hardly influence the effect of deflation: firstly, all the poles are left unchanged, and secondly, already a decrease of dominance of the found poles to nondominance (because of the projected in- and output vectors b _d and c _d ) will shrink the local convergence neighborhood of these poles significantly, again because of the convergence behavior of DPA [85].

This approach, however, may still suffer from the fact that the convergence behavior can be very local and hence may heavily depend on the initial estimates s ₀ ⁱ. Although in practice one often has rather accurate initial estimates of the poles of interest, this may be problematic if accurate information is not available. It may take many iterations until convergence if the initial estimate is not in the neighborhood of a dominant pole. On the other hand, the computational complexity of this problem depends on the costs of the LU factorization, which in certain practical examples can be computed very efficiently. In the next section a subspace accelerated version of DPA is described, that improves the global convergence by using search spaces.

3.2.4 Subspace Accelerated DPA

A drawback of DPA is that information obtained in the current iteration is discarded at the end of the iteration. The only information that is preserved is contained in the new pole estimate s _k+1. The current right and left approximate eigenvectors v _k and w _k , however, may also contain components in the direction of eigenvectors corresponding to other dominant poles. Instead of discarding these approximate eigenvectors, they are kept in search spaces spanned by the columns of V and W, respectively. This idea is known as subspace acceleration.

A global overview of SADPA is shown in Algorithm 4.3. Starting with a single shift s ₁, the first iteration is equivalent to the first iteration of the DPA (step 3–4). The right and left eigenvector approximations v ₁ and w ₁ are kept in spaces V and W. In the next iteration, these spaces are expanded orthogonally, by using modified Gram-Schmidt (MGS) [63], with the approximations v ₂ and w ₂ corresponding to the new shift s ₂ (step 5–6). Hence the spaces grow and will contain better approximations.

Algorithm 4.3 Subspace Accelerated DPA (SADPA)

It can be shown that subspace accelerated DPA, under certain conditions, is equivalent to subspace accelerated Rayleigh Quotient Iteration and the Jacobi-Davidson method, see [80, 85] for more details.

3.2.4.1 Selection Strategy

In iteration k the Petrov-Galerkin approach leads (step 7) to the projected eigenproblem

$$\displaystyle\begin{array}{rcl} W^{{\ast}}\mathit{AV }\tilde{\mathbf{x}}& =& \tilde{\lambda }W^{{\ast}}\mathit{EV }\tilde{\mathbf{x}}, {}\\ \tilde{\mathbf{y}}W^{{\ast}}\mathit{AV }& =& \tilde{\lambda }\tilde{\mathbf{y}}W^{{\ast}}\mathit{EV }. {}\\ \end{array}$$

Since the interaction matrices S = W ^∗ AV and T = W ^∗ EV are of low dimension k ≪ n, the eigentriplets $(\tilde{\lambda }_{i},\tilde{\mathbf{x}}_{i},\tilde{\mathbf{y}}_{i})$ of this reduced problem can be computed using the QZ method (or the QR method in the bi-E-orthogonal case) (step 1 of Algorithm 4.4). This provides k approximate eigentriplets $(\hat{\lambda }_{i} =\tilde{\lambda } _{i},\hat{\mathbf{x}}_{i} = V \tilde{\mathbf{x}}_{i},\hat{\mathbf{y}}_{i} = W\tilde{\mathbf{y}}_{i})$ for (A, E). The most natural thing to do is to choose the triplet $(\hat{\lambda }_{j},\hat{\mathbf{x}}_{j},\hat{\mathbf{y}}_{j})$ with the most dominant pole approximation (step 8–9): compute the corresponding residues $\hat{R}_{i} = (\mathbf{c}^{{\ast}}\hat{\mathbf{x}}_{i})(\hat{\mathbf{y}}_{i}^{{\ast}}\mathbf{b})$ of the k pairs and select the pole with the largest $\vert \hat{R}_{j}\vert /\vert \mbox{ Re}(\hat{\lambda }_{j})\vert$ (see Algorithm 4.4). The SADPA then continues with the new shift $s_{k+1} =\hat{\lambda } _{j}$ (step 16).

The residues $\hat{R}_{i}$ can be computed without computing the approximate eigenvectors explicitly (step 5 of Algorithm 4.4): if the $\tilde{\mathbf{x}}_{i}$ and $\tilde{\mathbf{y}}_{i}$ are scaled so that $\tilde{\mathbf{y}}_{i}^{{\ast}}T\tilde{\mathbf{x}}_{i} = 1$ ($=\hat{ \mathbf{y}}_{i}^{{\ast}}E\hat{\mathbf{x}}_{i}$), then it follows that the $\hat{R}_{i}$ can be computed as $\hat{R}_{i} = ((\mathbf{c}^{{\ast}}V )\tilde{\mathbf{x}}_{i})(\tilde{\mathbf{y}}_{i}^{{\ast}}(W^{{\ast}}\mathbf{b}))$ ($= (\mathbf{c}^{{\ast}}\hat{\mathbf{x}}_{i})(\hat{\mathbf{y}}_{i}^{{\ast}}\mathbf{b})$).

Instead of $\hat{\mathbf{y}}_{i}^{{\ast}}E\hat{\mathbf{x}}_{i} = 1$ one can also use the scaling $\|\hat{\mathbf{y}}_{i}\|_{2} =\|\hat{ \mathbf{x}}_{i}\|_{2} = 1$ when computing approximate residues. In that case the product of the angles $\angle (\hat{\mathbf{x}}_{i},\mathbf{c})$ and $\angle (\hat{\mathbf{y}}_{i},\mathbf{b})$ is used in the computation of the approximate residues (see also [85]), which numerically may be more robust.

Algorithm 4.4 $(\tilde{\varLambda },\tilde{X},\tilde{Y }) = \mbox{ Sort}(S,T,\mathbf{b},\mathbf{c})$

3.2.4.2 Deflation

In each iteration step a convergence test (step 10) is done like in DPAd (Algorithm 4.2): if for the selected eigentriplet $(\hat{\lambda }_{1},\hat{\mathbf{x}}_{1},\hat{\mathbf{y}}_{1})$ the norm of the residual $\vert \vert A\hat{\mathbf{x}}_{1} -\hat{\lambda }_{1}E\hat{\mathbf{x}}_{1}\vert \vert _{2}$ is smaller than some tolerance ε, it is converged. In general more than one dominant eigentriplet is wanted and it is desirable to avoid repeated computation of the same eigentriplet. The same deflation technique as used in DPAd can be applied here (steps 5–6 and 12–13 of Algorithm 4.5, see also Sect. 4.2.2.3), and since SADPA continues with b _d and c _d , no explicit E-orthogonalization of expansion vectors against found eigenvectors is needed in step 3 and 4. The effect is similar to the usual deflation in Jacobi-Davidson methods [62]: found eigenvectors are hard-locked, i.e. once deflated, they do not participate and do not improve during the rest of the process (contrary to soft-locking, where deflated eigenvectors still participate in the Rayleigh-Ritz (Ritz-Galerkin) procedure and may be improved, at the cost of additional computations and administration, see [69, 70]). In fact, there is cheap explicit deflation without the need for implicit deflation (cf. [62, remark 5, p. 106], where a combination of explicit and implicit deflation is used).

Algorithm 4.5 $(\varLambda,X,Y,\tilde{V },\tilde{W},\mathbf{b}_{d},\mathbf{c}_{d}) = \mbox{ Deflate}(\lambda,\mathbf{x},\mathbf{y},\varLambda,X,Y,V,W,E,\mathbf{b},\mathbf{c})$

If an eigentriplet has converged (steps 11–13 of Algorithm 4.3), the eigenvectors are deflated from the search spaces by reorthogonalizing the search spaces against the found eigenvectors. This can be done by using modified Gram-Schmidt (MGS) and by recalling that, if the exact vectors are found, the pencil

$$\displaystyle{ ((I -\mathit{EXY }^{{\ast}})A(I -\mathit{XY }^{{\ast}}E),\quad (I -\mathit{EXY }^{{\ast}})E(I -\mathit{XY }^{{\ast}}E)) }$$

has the same eigentriplets as (A, E), but with the found eigenvalues transformed to zero (Algorithm 4.6, see also [62, 67]). Since in finite arithmetic only approximations to exact eigentriplets are available, the computed eigenvalues are transformed to η ≈ 0. The possible numerical consequences of this, however, are limited, since SADPA continues with b _d and c _d , and as argued in Sect. 4.2.2.3, the residues of the found poles are transformed to (approximately) zero.

If a complex pole has converged, its complex conjugate is also a pole and the corresponding complex conjugate right and left eigenvectors can also be deflated. A complex conjugate pair is counted as one pole. The complete deflation procedure is shown in Algorithm 4.5.

After deflation of the found pole(s), SADPA continues with the second most dominant approximate pole (steps 13–16 of Algorithm 4.3).

Algorithm 4.6 V = Expand(V, X, Y, E, v)

3.2.4.3 Further Improvements and Remarks

It may happen that the search spaces V and W become high-dimensional, especially when a large number of dominant poles is wanted. A common way to deal with this is to do a thick restart [62, 87]: if the subspaces V and W reach a certain maximum dimension k _max  ≪ n, they are reduced to a dimension k _min  < k _max by keeping the k _min most dominant approximate eigentriplets; the process is restarted with the reduced V and W (already converged eigentriplets are not part of the active subspaces V and W). This procedure is repeated until all poles are found.

Furthermore, as more eigentriplets have converged, approximations of new eigentriplets may become poorer or convergence may be hampered, due to rounding errors in the orthogonalization phase and the already converged eigentriplets. It is therefore advised to take a small tolerance ε ≤ 10⁻¹⁰. Besides that, as the estimate converges to a dominant pole, the right and left eigenvectors computed in step 3 and 4 of Algorithm 4.3 are usually more accurate than the approximations computed in the selection procedure: if the estimate s _k is close to an eigenvalue λ, then s _k E − A may become ill-conditioned, but, as is discussed in [79] and [78, Section 4.3], the solutions v _k and w _k have large components in the direction of the corresponding right and left eigenvectors (provided b and c have sufficiently large components in those directions). In the deflation phase, it is therefore advised to take the most accurate of both, i.e., the approximate eigenvector with smallest residual. It may also be advantageous to do an additional step of two-sided Rayleigh quotient iteration to improve the eigenvectors.

SADPA requires only one initial estimate. If rather accurate initial estimates are available, one can take advantage of this in SADPA by setting the next estimate after deflation to a new initial estimate (step 16 of Algorithm 4.3).

Every iteration, two linear systems are to be solved (step 3 and 4). As was already mentioned, this can efficiently be done by computing one LU-factorization and solving the systems by using L and U, and U ^∗ and L ^∗, respectively. Because in practice the system matrices A and E are often very sparse and structured, computation of the LU-factorizations can be relatively inexpensive.

The selection criterion can easily be changed to another of the several existing indices of modal dominance [57, 64, 94]. Furthermore, the strategy can be restricted to considering only poles in a certain frequency range. Also, instead of providing the number of wanted poles, the procedure can be automated even further by providing the desired maximum error | H(s) − H _k (s) | for a certain frequency range: the procedure continues computing new poles until the error bound is reached. Note that such an error bound requires that the transfer function of the complete model can be evaluated efficiently for the frequency range of interest.

3.2.4.4 A Numerical Example

For illustrational purposes, SADPA was applied to a transfer function of the New England test system, a model of a power system. This small benchmark system has 66 state variables (for more information, see [72]). The tolerance used was $\epsilon = 10^{-10}$ and no restarts were used. Every iteration, the pole approximation $\hat{\lambda }_{j}$ with largest $\vert \hat{R}_{j}\vert /\vert \mbox{ Re}(\hat{\lambda }_{j})\vert$ was selected. Table 4.1 shows the found dominant poles and the iteration number for which the pole satisfied the stopping criterion. Bodeplots of two modal equivalents are shown in Fig. 4.9. The quality of the modal equivalent increases with the number of found poles, as can be observed from the better match of the exact and reduced transfer function.

Table 4.1 Results for SADPA applied to the New England test system (s ₁ = 1i)

Fig. 4.9

Bode plot of 5th order (left) and 11th order (right) modal equivalent, complete model and error for the transfer function of the New England test system (66 states in the complete model)

3.3 Generalizations to Other Eigenvalue Problems

In this section, four variants of the dominant pole algorithm presented in the previous section are briefly discussed. In Sect. 4.2.3.1, the theory is extended to multi-input multi-output systems. A variant of DPA that computes the dominant zeros of a transfer function is described in Sect. 4.2.3.2. Section 4.2.3.3 describes the extension to higher-order dynamical systems. Finally, in Sect. 4.2.3.4 it is shown how DPA can be used for the computation of eigenvalues most sensitive to parameter changes.

3.3.1 MIMO Systems

For a multi-input multi-output (MIMO) system

$$\displaystyle{ \left \{\begin{array}{lll} E\dot{\mathbf{x}}(t)& =&A\mathbf{x}(t) + B\mathbf{u}(t)\\ \mathbf{y}(t)&=&C^{{\ast} } \mathbf{x} (t) + D\mathbf{u} (t), \end{array} \right. }$$

where $A,E \in \mathbb{R}^{n\times n}$, $B \in \mathbb{R}^{n\times m}$, $C \in \mathbb{R}^{n\times p}$, $\mathbf{x}(t) \in \mathbb{R}^{n}$, $\mathbf{u}(t) \in \mathbb{R}^{m}$, $\mathbf{y}(t) \in \mathbb{R}^{p}$ and $D \in \mathbb{R}^{p\times m}$, the transfer function $H(s): \mathbb{C} \rightarrow \mathbb{C}^{p\times m}$ is defined as

$$\displaystyle{ H(s) = C^{{\ast}}(\mathit{sE} - A)^{-1}B + D. }$$

(4.34)

The dominant poles of (4.34) are those $s \in \mathbb{C}$ for which the largest singular value $\sigma _{\max }(H(s)) \rightarrow \infty$. For square transfer functions (m = p), there is an equivalent criterion: the dominant poles are those $s \in \mathbb{C}$ for which the absolute smallest eigenvalue $\vert \lambda _{\min }(H^{-1}(s))\vert \rightarrow 0$. This leads, for square transfer functions, to the following Newton scheme:

$$\displaystyle{ s_{k+1} = s_{k} -\frac{1} {\mu _{\min }} \frac{1} {\mathbf{v}^{{\ast}}C^{{\ast}}(s_{k}E - A)^{-2}B\mathbf{u}}, }$$

where $(\mu _{\min },\mathbf{u},\mathbf{v})$ is the eigentriplet of $H^{-1}(s_{k})$ corresponding to $\lambda _{\min }(H^{-1}(s_{k}))$. For a dominant pole, the mountain spreads of σ _max are larger and, therefore, the neighborhood of convergence attraction is larger than for a less dominant pole, which would show just a spike. An algorithm for computing the dominant poles of a MIMO transfer function can be readily derived from Algorithm 4.1. The reader is referred to [74] for the initial MIMO DPA algorithm and to [81] for an algorithm SAMDP, similar to SADPA, generalizations to non-square MIMO systems and more details.

3.3.2 Computing the Zeros of a Transfer Function

The zeros of a transfer function $H(s) = \mathbf{c}^{{\ast}}(\mathit{sE} - A)^{-1}\mathbf{b} + d$ are those $s \in \mathbb{C}$ for which H(s) = 0. An algorithm, similar to Algorithm 4.1, can be derived by noting that a Newton scheme for computing the zeros of a transfer function is given by

$$\displaystyle{ s_{k+1} = s_{k} + \frac{\mathbf{c}^{{\ast}}(s_{k}E - A)^{-1}\mathbf{b} + d} {\mathbf{c}^{{\ast}}(s_{k}E - A)^{-2}\mathbf{b}}. }$$

(4.35)

In fact, it can be shown that the dominant zeros can be computed as the dominant poles of the inverse transfer function $[H(s)]^{-1} = \mathbf{c}_{z}^{{\ast}}(\mathit{sE}_{z} - A_{z})^{-1}\mathbf{b}_{z} + d_{z}$, which has the realization

$$\displaystyle\begin{array}{rcl} A_{z} = \left [\begin{array}{*{10}c} A &\mathbf{b}\\ \mathbf{c} ^{T }& d \end{array} \right ],& E_{z} = \left [\begin{array}{*{10}c} E &0\\ 0 &0 \end{array} \right ],& {}\\ \mathbf{b}_{z} = \left [\begin{array}{*{10}c} 0\\ -1 \end{array} \right ],& \mathbf{c}_{z} = \left [\begin{array}{*{10}c} 0\\ 1 \end{array} \right ], & d_{z} = 0,{}\\ \end{array}$$

In other words, the dominant zeros of H(s) can be computed by applying DPA to [H(s)]⁻¹. See [73] for further details.

3.3.3 Polynomial Eigenvalue Problems

The main idea of using Newton’s method to find dominant poles can be generalized to higher order systems [84]. For the second-order transfer function $H(s) = \mathbf{c}^{{\ast}}(s^{2}M + \mathit{sC} + K)^{-1}\mathbf{b}$, for instance, the scheme becomes

$$\displaystyle\begin{array}{rcl} s_{k+1}& =& s_{k} - \frac{\mathbf{c}^{{\ast}}\mathbf{v}} {\mathbf{w}^{{\ast}}(2s_{k}M + C)\mathbf{v}}, {}\\ \end{array}$$

where $\mathbf{v} = (s_{k}^{2}M + s_{k}C + K)^{-1}\mathbf{b}$ and $\mathbf{w} = (s_{k}^{2}M + s_{k}C + K)^{-{\ast}}\mathbf{c}$. The efficient use of subspace acceleration on large scale second-order eigenvalue problems is described in [84].

3.3.4 Computing Eigenvalues Sensitive to Parameter Changes

Let $p \in \mathbb{R}$ be a system parameter (e.g., a resistor value R, or 1∕R, in an electric circuit), and let A(p) and E(p) be matrices that depend on p. The derivative of an eigenvalue λ of the pencil (A(p), E(p)), with left and right eigenvectors $\mathbf{y} \equiv \mathbf{y}(p)$ and $\mathbf{x} \equiv \mathbf{x}(p)$, to a parameter p is given by [66, 75]

$$\displaystyle{ \frac{\partial \lambda } {\partial p} = \frac{\mathbf{y}^{{\ast}}(\frac{\partial A} {\partial p} -\lambda \frac{\partial E} {\partial p} )\mathbf{x}} {\mathbf{y}^{{\ast}}E\mathbf{x}}. }$$

(4.36)

The derivative (4.36) is often called the sensitivity (coefficient) of λ. Assuming that $\frac{\partial E} {\partial p} = 0$, with y and x scaled so that y ^∗ E x = 1, the eigenvalue derivative (4.36) becomes

$$\displaystyle{ \frac{\partial \lambda } {\partial p} = \mathbf{y}^{{\ast}}\frac{\partial A} {\partial p} \mathbf{x}. }$$

(4.37)

The larger the magnitude of the derivative (4.37), the more sensitive eigenvalue λ is to changes in parameter p. In practical applications such information is useful when, for instance, a system needs to be stabilized by moving poles from the right half-plane to the left half-plane [83, 95].

Suppose that the derivative of A to parameter p has rank 1 and hence can be written as

$$\displaystyle{ \frac{\partial A} {\partial p} = \mathbf{b}\mathbf{c}^{{\ast}}, }$$

(4.38)

where $\mathbf{b},\mathbf{c} \in \mathbb{R}^{n}$ are vectors. Then the sensitivity of an eigenvalue λ with left and right eigenvectors y and x (with y ^∗ E x = 1) becomes

$$\displaystyle{ \frac{\partial \lambda } {\partial p} = \mathbf{y}^{{\ast}}\frac{\partial A} {\partial p} \mathbf{x} = (\mathbf{y}^{{\ast}}\mathbf{b})(\mathbf{c}^{{\ast}}\mathbf{x}) = (\mathbf{c}^{{\ast}}\mathbf{x})(\mathbf{y}^{{\ast}}\mathbf{b}). }$$

(4.39)

In the right-hand side of (4.39) one recognizes the residues of the transfer function $H(s) = \mathbf{c}^{{\ast}}(\mathit{sE} - A)^{-1}\mathbf{b}$. Consequently, the most sensitive eigenvalues of the pencil (A(p), E) can be computed by applying DPA to (E, A, b, c), with b and c defined by (4.38).

If $\frac{\partial A} {\partial p}$ has rank higher than 1, one can change Algorithm 4.1 as follows to compute the most sensitive eigenvalues: replace b and c by $\frac{\partial A} {\partial p} \mathbf{v}_{k-1}$ and $\left (\frac{\partial A} {\partial p} \mathbf{w}_{k-1}\right )^{{\ast}}$, respectively. The algorithm based on this is called SASPA. For more details and generalizations to higher rank derivatives and multiparameter systems, see [83].

Having obtained, with the use of SADPA [82] or SAMDP [81], a reduced model for a large scale system incorporating feedback controllers at nominal parameters, one may want to find other reduced models for off-nominal parameters in these controllers. The SADPA and SAMDP are ideal algorithms for this application, since they benefit from the reduced model information for the nominal parameters. Note that only a true modal equivalent can benefit from this sensitivity feature, through the use of the SASPA [83].

3.4 Improving Krylov Models by Using Dominant Poles

It is well known that for some examples moment matching works well, while reduced order models computed by modal approximation are of low quality, and the other way around [58, 80]. Generally speaking, modal approximation performs best if there are k ≪ n dominant poles with residues much larger than the residues of the non-dominant poles. In other words, there is a k ≪ n for which one has $\vert R_{1}\vert \geq \vert R_{2}\vert \geq \ldots \geq \vert R_{k}\vert \gg \vert R_{k+1}\vert \geq \vert R_{n-1}\vert \geq \vert R_{n}\vert$, so that truncation at the kth pole does not give a large error [64]. Moment matching based approaches, on the other hand, perform best if the moments show a similar steep decay. There is, however, one additional complication for Krylov based moment matching approaches, that is best explained by an example. Figure 4.10 shows the Bode magnitude plots of an exact transfer function and of two reduced order models: one modal approximation and a moment matching approximation. While the modal approximation captures the dominant dynamics, the moment matching model deviates for ω > 4 rad/s.

Fig. 4.10

Frequency response of complete system (n = 66), modal approximation (k = 12), and dual Arnoldi model (k = 30)

Fig. 4.11

Relevant part of pole spectrum of complete system (n = 66), modal approximation (k = 12), and dual Arnoldi model (k = 30)

The modal approximation matches the original transfer function well because it is built from the 7 most dominant poles. The moment matching Arnoldi model (k = 30) was built using left and right Krylov subspaces with shift s ₀ = 0. Therefore, the match for frequencies up to ω = 4 rad/s is good. For higher frequencies, however, this approach suffers from a well known property of Arnoldi methods, that were originally developed for the computation of eigenvalues: the eigenvalue approximations, or Ritz values, tend to approximate the eigenvalues at the outside of the spectrum [93]. This can also be seen in Fig. 4.11, where the circles denote the poles of the moment matching model (note the inverses of the poles are shown): they match the eigenvalues at the outside. The dominant poles, however, may be located anywhere in the spectrum, as can also be seen in Fig. 4.11 (squares). This explains why the Arnoldi model fails to capture the peaks.

Based on the above observations and theory in [65], the idea is to use the imaginary parts of dominant poles as shifts for the rational Krylov approach, so that resonance peaks located well within the system frequency bandwidth can also be captured by Krylov methods. The combined dominant pole – Krylov approach can be summarized as follows:

• 1. Compute k ≪ n dominant poles $\lambda _{j} =\alpha _{j} \pm \beta _{j}i$, with j = 1, … k and $i = \sqrt{-1}$.

• 2. Choose interpolation points $s_{j} =\beta _{j}i$.

• 3. Construct $V _{j},W_{j} \in \mathbb{C}^{n\times k_{j}}$ such that their columns are bases for the rational Krylov [86] spaces

  $$\displaystyle\begin{array}{rcl} & & \qquad \mbox{ colspan}(V _{j}) = \mathcal{K}^{k_{j} }((s_{j}E - A)^{-1}E,(s_{ j}E - A)^{-1}\mathbf{b}) {}\\ & & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \mbox{ and} {}\\ & & \mbox{ colspan}(W_{j}) = \mathcal{K}^{k_{j} }((s_{j}E - A)^{-{\ast}}E^{{\ast}},(s_{ j}E - A)^{-{\ast}}\mathbf{c}), {}\\ \end{array}$$

  respectively.

• 4. Project with $V = \mbox{ orth}([V _{1},\ldots,V _{k}])$ and $W = \mbox{ orth}([W_{1},\ldots,W_{k}])$, where orth constructs an orthogonal basis for the spaces. The size of the reduced model is at most $K =\sum _{ j=1}^{k}k_{j}$, matching 2K moments.

Fig. 4.12

Bode plot (with modulus and phase) of the modal equivalent, the complete model and the error for the transfer function P _sc (s)∕B _sc (s) of BIPS (41 in the modal equivalent, 1664 in the complete model)

Fig. 4.13

Step responses for transfer function P _sc (s)∕B _sc (s) of BIPS, complete model and modal equivalent (41 states in the modal equivalent, 1664 in the complete model, step disturbance of 0. 01 pu)

3.5 Numerical Examples

3.5.1 Brazilian Interconnected Power System (BIPS)

The Brazilian Interconnected Power System (BIPS) is a year 1999 planning model that has been used in practice (see [82] for more technical details). The size of the sparse matrices A and E is n = 13, 251 (the number of states in the dense state space realization is 1, 664). The corresponding transfer function has a non-zero direct transmission term d. Figure 4.12 shows the frequency response of the complete model and the reduced model (41 states) together with the error. Both the magnitude and the phase plots show good matches of the exact and the reduced transfer functions (a relative error of approximately $\vert \vert H(s) - H_{k}(s)\vert \vert /\vert \vert H_{k}(s)\vert \vert = 0.1$, also for the DC-gain H(0)). Figure 4.13 shows the corresponding step response (step u = 0. 01).¹⁵ The reduced model nicely captures the system oscillations. The reduced model (30 poles, 56 states) was computed by SADPA in 341 LU-factorizations (k _min  = 1, k _max  = 10). This reduced model could be reduced further to 41 states (22 poles) by removing less dominant contributions, without decreasing the quality of the reduced model much.

3.5.1.1 Sensitivity of BIPS

To study the sensitivity of the dominant poles and system stability of BIPS, the gain (Kpss) of one of the generators is varied between 0 and 30, with increments of 0. 5. Figure 4.14 shows the traces for the most sensitive poles as computed by SASPA (Sect. 4.2.3.4, see also [83]). The CPU time needed for the 60 runs was 1,450 s. A root-locus plot for all poles, computed using the QR method, confirmed that the most sensitive poles were found, but needed 33,600 s. Hence, for large-scale systems, SASPA is a very effective and efficient way to produce relevant root-locus plots.

Fig. 4.14

Root locus plot of sensitive poles computed by SASPA. As the gain increases, the critical rightmost pole crosses the imaginary axis and the 5 % damping ratio boundary. Squares denote initial pole locations

3.5.2 The Breathing Sphere

Figure 4.15 shows the frequency response of a 70th order Second-Order Arnoldi [59] reduced model of vibrating body from sound radiation analysis (n = 17, 611 degrees of freedom, see [71]), that was computed using the complex parts i β of five dominant poles $\lambda =\alpha +i\beta$ (computed by Quadratic DPA [84]) as interpolation points, as described in Sect. 4.2.4. This model is more accurate than reduced order models based on standard Krylov methods and matches the peaks up to ω = 1 rad/s, because of use of shifts near the resonance frequencies. This model is a good example of the combined dominant pole – rational Krylov approach, since modal approximations of similar quality require too much CPU time, while Krylov models with uniformly spaced shifts do not capture the peaks.

Fig. 4.15

Exact and reduced system transfer functions for a vibrating body, computed by a rational Krylov method with resonance frequencies as complex interpolation points

3.6 Concluding Remarks

In this chapter eigenvalue methods, based on the Dominant Pole Algorithm, for the computation of a few specific eigenvalues were discussed. The methods can be used to solve large-scale eigenvalue problems arising in real-life applications and simulation of dynamical systems, for instance for the computation of transfer function dominant poles and zeros, and eigenvalues most sensitive to parameter changes. Furthermore, the corresponding eigenvectors can be used for construction of reduced-order models (modal equivalents) or to improve Krylov-based models. The dominant poles can be used to determine shifts in rational Krylov methods for computing reduced-order models. The practical application of the algorithms was illustrated by numerical experiments with real-life examples.

4 Passivity Preserving Model Order Reduction

In this Section we are concerned with dynamical systems $\sum = (\mathbf{E},\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D})$ of the form

$$\displaystyle{ \left \{\begin{array}{ccc} \mathbf{E}\dot{\mathbf{x}}(t)& =& \mathbf{A}\mathbf{x}(t) + \mathbf{B}\mathbf{u}(t)\\ \mathbf{y} (t) & = &\mathbf{C} ^{{\ast} } \mathbf{x} (t) + \mathbf{D} \mathbf{u} (t), \end{array} \right. }$$

(4.40)

where $\mathbf{A},\mathbf{E} \in \mathbb{R}^{n\times n}$, E may be singular (we assume E is symmetric and positive (semi) definite), $\mathbf{B} \in \mathbb{R}^{n\times m}$, $\mathbf{C} \in \mathbb{R}^{n\times p}$, $\mathbf{D} \in \mathbb{R}^{p\times m}$, $\mathbf{x}(t) \in \mathbb{R}^{n}$, $\mathbf{y}(t) \in \mathbb{R}^{p}$ and $\mathbf{u}(t) \in \mathbb{R}^{m}$.¹⁶ The matrix E is called the descriptor matrix, the matrix A is called the state space matrix, the matrices B and C are called the input and output map, respectively, and D is the direct transmission map. The vectors u(t) and x(t) are called the input and the state vector, respectively, and y(t) is called the output of the system. The dimension n of the state is defined as the complexity of the system ∑. These systems often arise in circuit simulation, for instance, and in this application the system ∑ is often passive.¹⁷

The transfer function $\mathbf{G}: \mathbb{C}^{m} \rightarrow \mathbb{C}^{p}$, of (4.40),

$$\displaystyle{\mathbf{G}(s) = \mathbf{C}^{{\ast}}(s\mathbf{E} -\mathbf{A})^{-1}\mathbf{B} + \mathbf{D},}$$

can be obtained by applying the Laplace transform to (4.40) under the condition x(0) = 0. The transfer function relates outputs to inputs in the frequency domain via Y(s) = G(s)U(s), where Y(s) and U(s) are the Laplace transforms to y(t) and u(t), respectively.

We want to reduce the original system ∑ to a reduced order model $\hat{\sum }= (\hat{\mathbf{E}},\hat{\mathbf{A}},\hat{\mathbf{B}},\hat{\mathbf{C}},\mathbf{D})$

$$\displaystyle{ \left \{\begin{array}{ccc} \hat{E}\dot{\hat{\mathbf{x}}}(t)& =& \hat{A}\hat{\mathbf{x}}(t) +\hat{ B}\mathbf{u}(t)\\ \hat{\mathbf{y} }(t) & = &\hat{\mathbf{C} }^{{\ast} } \hat{\mathbf{x} }(t) + D\mathbf{u} (t), \end{array} \right. }$$

(4.41)

where $\hat{\mathbf{A}},\hat{\mathbf{E}} \in \mathbb{R}^{k\times k}$, $\hat{\mathbf{B}} \in \mathbb{R}^{k\times m}$, $\hat{\mathbf{C}} \in \mathbb{R}^{k\times p}$, $\mathbf{D} \in \mathbb{R}^{p\times m}$, $\hat{\mathbf{x}}(t) \in \mathbb{R}^{k}$, $\hat{\mathbf{y}}(t) \in \mathbb{R}^{p}$, $\mathbf{u}(t) \in \mathbb{R}^{m}$ and k ≪ n.

It is important to produce a reduced model that preserves stability and passivity.

Remark 4.1

Throughout the reminder of this chapter it is assumed that:

• m = p such that $\mathbf{B} \in \mathbb{R}^{n\times p}$, $\mathbf{C} \in \mathbb{R}^{p\times n}$ and $\mathbf{D} \in \mathbb{R}^{p\times p}$.

• A is a stable matrix i.e. Re(λ _i ) < 0 with λ _i  ∈ σ(A), i = 1, ⋯ , n.

• The system ∑ is observable and controllable [112] and it is passive.

Spectral zeros play an important role in guaranteeing passivity as will be explained in the next sections. In Section 4.3.3 the spectral zeros and the method for computing them are introduced. In the following we describe two projection reduced order methods from literature for reducing the system, that aim to produce a reduced transfer function, which has the specified roots at selected spectral zeros. These methods have been developed by Sorensen [110] and Antoulas [96].

4.1 Model Reduction via Projection Matrices

We assume that $\mathcal{M}$ and $\mathcal{N}$ are k-dimensional subspaces of $\mathbb{R}^{n}$. V and W are built for reducing the system by a projection method. So we construct $\mathbf{V} =\{ \mathbf{v}_{1},\cdots \,,\mathbf{v}_{k}\} \in \mathbb{R}^{n\times k}$, of which the column vectors v _i form a basis of $\mathcal{M}$, and $\mathbf{W} =\{ \mathbf{w}_{1},\cdots \,,\mathbf{w}_{k}\} \in \mathbb{R}^{n\times k}$, of which the column vectors w _j form a basis of $\mathcal{N}$ (we are interested in $W^{{\ast}}V = I_{k}$). We assume that V and W are time-invariant.

We suppose $\mathbf{x} \in \mathcal{M}$ is an approximate solution of Σ. Hence we can write $\mathbf{x} = \mathbf{V}\hat{\mathbf{x}}$,

where $\hat{\mathbf{x}} \in \mathbb{R}^{k}$ and $\dot{\mathbf{x}} = \mathbf{V}\dot{\hat{\mathbf{x}}}$. Then the residual is

$$\displaystyle{\mathbf{E}\dot{\mathbf{x}} -\mathbf{A}\mathbf{x} -\mathbf{B}\mathbf{u} = \mathbf{E}\mathbf{V}\dot{\hat{\mathbf{x}}} -\mathbf{A}\mathbf{V}\hat{\mathbf{x}} -\mathbf{B}\mathbf{u}.}$$

Next, we assume that this residual is orthogonal to $\mathcal{N}$

$$\displaystyle{\begin{array}{cccc} & \mathbf{W}^{{\ast}}(\mathbf{E}\mathbf{V}\dot{\hat{\mathbf{x}}} -\mathbf{A}\mathbf{V}\hat{\mathbf{x}} -\mathbf{B}\mathbf{u}) & =&\mathbf{0}, \\ \Rightarrow &\mathbf{W}^{{\ast}}\mathbf{E}\mathbf{V}\dot{\hat{\mathbf{x}}} -\mathbf{W}^{{\ast}}\mathbf{A}\mathbf{V}\hat{\mathbf{x}} -\mathbf{W}^{{\ast}}\mathbf{B}\mathbf{u}& =&\mathbf{0}. \end{array} }$$

Then the reduced model $\hat{\varSigma }$ becomes:

$$\displaystyle{ \left \{\begin{array}{ccc} \hat{\mathbf{E}}\dot{\hat{\mathbf{x}}}(t)& =& \hat{\mathbf{A}}\hat{\mathbf{x}}(t) +\hat{ \mathbf{B}}\mathbf{u}(t),\\ \hat{\mathbf{y} }(t) & = &\hat{\mathbf{C} }^{{\ast} } \hat{\mathbf{x} }(t) + \mathbf{D} \mathbf{u} (t), \end{array} \right. }$$

where $\hat{\mathbf{A}} = \mathbf{W}^{{\ast}}\mathbf{A}\mathbf{V} \in \mathbb{R}^{k\times k},\hat{\mathbf{E}} = \mathbf{W}^{{\ast}}\mathbf{E}\mathbf{V} \in \mathbb{R}^{k\times k}$, $\hat{\mathbf{B}} = \mathbf{W}^{{\ast}}\mathbf{B} \in \mathbb{R}^{k\times m}$, $\hat{\mathbf{C}} = \mathbf{C}\mathbf{V} \in \mathbb{R}^{k\times p}$, $\hat{\mathbf{x}}(t) = \mathbf{V}\hat{\mathbf{x}} \in \mathbb{R}^{k}$ and $\mathbf{y} =\hat{ \mathbf{y}}(t) \in \mathbb{R}^{p}$ [105].

4.2 Passive Systems

We can reduce the model by V and W, which are constructed in the previous Sect. 4.3.1. With arbitrary V and W, some features of the original system may not be preserved. One of these properties, which we are interested in to preserve, is passivity.

The matrix A is assumed to be stable, which means all its eigenvalues are in the open left half-plane. Passivity is defined using an energy concept.

Definition 4.3

A system is passive if it does not generate energy internally, and strictly passive if it consumes or dissipates input energy [110].

In other words Σ is passive if

$$\displaystyle{\mathit{Re}\int _{-\infty }^{t}\mathbf{u}(\tau )^{{\ast}}\mathbf{y}(\tau )d\tau \geq 0,\quad \quad \forall t \in \mathbb{R},\quad \forall \mathbf{u} \in \mathcal{L}_{ 2}(\mathbb{R})}$$

or strictly passive if

$$\displaystyle{\exists \delta> 0\quad \mbox{ s.t. }\mathit{Re}\int _{-\infty }^{t}\mathbf{u}(\tau )^{{\ast}}\mathbf{y}(\tau )d\tau \geq \delta \;\cdot \mathit{Re}\int _{ -\infty }^{t}\mathbf{u}(\tau )^{{\ast}}\mathbf{u}(\tau )d\tau,\;\;\forall t \in \mathbb{R},\;\;\forall \mathbf{u} \in \mathcal{L}_{ 2}(\mathbb{R})}$$

Another more practical definition of passivity is based on the transfer function G(s) in the frequency domain:

Definition 4.4

[110] The system Σ is passive iff the transfer function G(s) is positive real, which means that:

• 1. G(s) is analytic for Re(s) > 0,

• 2. $\mathbf{G}(\bar{s}) = \overline{\mathbf{G}(s)}$, $\forall s \in \mathbb{C}$,

• 3. G(s) + (G(s))^∗ ≥ 0 for Re(s) > 0 where

  $$\displaystyle{(\mathbf{G}(s))^{{\ast}} = \mathbf{B}^{{\ast}}(s\mathbf{E}^{{\ast}}-\mathbf{A}^{{\ast}})^{-1}\mathbf{C} + \mathbf{D}^{{\ast}}.}$$

We try to construct the V and W in such a way that the transfer function of the reduced model has the above three properties. Property 3 implies the existence of a stable rational matrix function $\mathbf{K}(s) \in \mathbb{R}^{p\times p}$ (with stable inverse) such that

$$\displaystyle{\mathbf{G}(s) + (\mathbf{G}(-s))^{{\ast}} = \mathbf{K}(s)\mathbf{K}^{{\ast}}(-s).}$$

We prove this only for the scalar case p = 1 of the transfer function. Let G(s) be a scalar, positive-real transfer function with real coefficients. The spectral zeros of G are defined as the zeros of $G(s) + G^{{\ast}}(-s)$. Since all coefficients of G are real, we have $G^{{\ast}}(-s) = G(-s)$. Since G(s) is scalar, we can write $G(s) = \frac{n(s)} {d(s)}$, where n(s) and d(s) are polynomials of degree ≤ k + 1 (in this note we assume k is even; a similar explanation holds when k is odd). Note that $(G(-s))^{{\ast}} = \frac{n^{{\ast}}(-s)} {d^{{\ast}}(-s)}$. Now we have

$$\displaystyle\begin{array}{rcl} G(s) + (G(-s))^{{\ast}}& =& \frac{n(s)} {d(s)} + \frac{n^{{\ast}}(-s)} {d^{{\ast}}(-s)} \\ & =& \frac{n(s)d^{{\ast}}(-s) + d(s)n^{{\ast}}(-s)} {d(s)d^{{\ast}}(-s)} \\ & =& \frac{r(s)r^{{\ast}}(-s)} {d(s)d^{{\ast}}(-s)}. {}\end{array}$$

(4.42)

We focus on proving (4.42). We will use the following identies:

$$\displaystyle\begin{array}{rcl} n(s)& =& \sum _{i=0}^{k/2}\nu _{ 2i}s^{2i} +\sum _{ i=0}^{k/2}\nu _{ 2i+1}s^{2i+1} = A + B, {}\\ d(s)& =& \sum _{i=0}^{k/2}\delta _{ 2i}s^{2i} +\sum _{ i=0}^{k/2}\delta _{ 2i+1}s^{2i+1} = C + D. {}\\ & & {}\\ \end{array}$$

It is easy to see that

$$\displaystyle\begin{array}{rcl} n(-s)& =& \sum _{i=0}^{k/2}\nu _{ 2i}s^{2i} -\sum _{ i=0}^{k/2}\nu _{ 2i+1}s^{2i+1} = A - B, {}\\ d(-s)& =& \sum _{i=0}^{k/2}\delta _{ 2i}s^{2i} -\sum _{ i=0}^{k/2}\delta _{ 2i+1}s^{2i+1} = C - D. {}\\ & & {}\\ \end{array}$$

For the sum $n(s)d(-s) + n(-s)d(s)$ we then have

$$\displaystyle\begin{array}{rcl} n(s)d(-s) + n(-s)d(s)& =& (A + B)(C - D) + (A - B)(C + D)\,=\,2AC - 2BD {}\\ & =& 2\left [\sum _{i=0}^{k/2}\nu _{ 2i}s^{2i}\right ]\left [\sum _{ i=0}^{k/2}\delta _{ 2i}s^{2i}\right ] {}\\ & & -2\left [\sum _{i=0}^{k/2}\nu _{ 2i+1}s^{2i+1}\right ]\left [\sum _{ i=0}^{k/2}\delta _{ 2i+1}s^{2i+1}\right ] {}\\ & =& \tilde{v}(s) -\tilde{ w}(s). {}\\ \end{array}$$

Note that

$$\displaystyle\begin{array}{rcl} \tilde{v}(s)& =& \alpha _{0} +\alpha _{1}s^{2} +\alpha _{ 2}s^{4} + \cdots +\alpha _{ k}s^{2k}, {}\\ \tilde{w}(s)& =& \beta _{1}s^{2} +\beta _{ 2}s^{4} +\beta _{ 3}s^{6} + \cdots +\beta _{ k+1}s^{2k+2}. {}\\ \end{array}$$

So, we have

$$\displaystyle\begin{array}{rcl} t(s):=\tilde{ v}(s) -\tilde{ w}(s) =\alpha _{0} + (\alpha _{1} -\beta _{1})s^{2} + \cdots + (\alpha _{ k} -\beta _{k})s^{2k} -\beta _{ k+1}s^{2k+2}.& & {}\\ \end{array}$$

Clearly, if s ₀ is a zero of t(s), so is − s ₀. Consequently, we can factorize t(s) as $t(s) = r(s)r(-s)$. Summarizing, we finally have

$$\displaystyle\begin{array}{rcl} n(s)d(-s) + n(-s)d(s) =\tilde{ v}(s) -\tilde{ w}(s) = t(s) = r(s)r(-s),& & {}\\ \end{array}$$

which proves (4.42). ■ 

This last result equals K(s)K ^∗(−s), i.e., this is the spectral factorization of G. Here K is a called the spectral factor of G. The zeros of K, i.e. the λ _i , i = 1, ⋯ , n such that det(K(λ _i )) = 0, are the spectral zeros of G.

4.3 Spectral Zeros and Generalized Eigenvalue Problem

We start this section with explaining a generalized eigenvalue problem, which Sorensen used in [110]. It brings together the theory of positive real interpolation by Antoulas [96] and the invariant subspace method for interpolating the spectral zeros by Sorensen.

First we recall that for the transfer function G(s) we have

$$\displaystyle\begin{array}{rcl} \mathbf{G}(s)& =& \mathbf{C}^{{\ast}}(s\mathbf{E} -\mathbf{A})^{-1}\mathbf{B} + \mathbf{D},\;\;\;\mbox{ and thus}, {}\\ (\mathbf{G}(-s))^{{\ast}}& =& \mathbf{B}^{{\ast}}(-s\mathbf{E}^{{\ast}}-\mathbf{A}^{{\ast}})^{-1}\mathbf{C} + \mathbf{D}^{{\ast}}, {}\\ & =& \mathbf{B}^{{\ast}}(s\mathbf{E}^{{\ast}}- (-\mathbf{A}^{{\ast}}))^{-1}(-\mathbf{C}) + \mathbf{D}^{{\ast}}. {}\\ \end{array}$$

Then we compute G + G ^∗,¹⁸

$$\displaystyle\begin{array}{rcl} & \begin{array}{ccc} \mathbf{G}(s) + (\mathbf{G}(-s))^{{\ast}}& =& (\mathbf{C}^{{\ast}}(s\mathbf{E} -\mathbf{A})^{-1}\mathbf{B} + \mathbf{D}) + (\mathbf{B}^{{\ast}}(s\mathbf{E}^{{\ast}}- (-\mathbf{A}^{{\ast}}))^{-1}(-\mathbf{C}) + \mathbf{D}^{{\ast}})\\ && \\ & =&\left [\begin{array}{cc} \mathbf{C}^{{\ast}}&\mathbf{B}^{{\ast}} \end{array} \right ]\left [\begin{array}{cc} (s\mathbf{E} -\mathbf{A})^{-1}& 0 \\ 0 &(s\mathbf{E}^{{\ast}}- (-\mathbf{A}^{{\ast}}))^{-1} \end{array} \right ]\left [\begin{array}{c} \mathbf{B}\\ - \mathbf{C} \end{array} \right ] + (\mathbf{D} + \mathbf{D}^{{\ast}}) \\ \end{array} & {}\\ & \qquad \qquad \begin{array}{ccc} & =&\left [\begin{array}{cc} \mathbf{C}^{{\ast}}&\mathbf{B}^{{\ast}} \end{array} \right ]\left (s\left [\begin{array}{cc} \mathbf{E}& 0\\ 0 &\mathbf{E} ^{{\ast}} \end{array} \right ] -\left [\begin{array}{cc} \mathbf{A}& 0\\ 0 & - \mathbf{A}^{{\ast}} \end{array} \right ]\right )^{-1}\left [\begin{array}{c} \mathbf{B}\\ - \mathbf{C} \end{array} \right ] + (\mathbf{D} + \mathbf{D}^{{\ast}}).\end{array}& {}\\ \end{array}$$

Note that this is the transfer function of the following system:

$$\displaystyle{ \left \{\begin{array}{ccc} \left [\begin{array}{cc} \mathbf{E}& 0\\ 0 &\mathbf{E} ^{{\ast} } \end{array} \right ]\dot{\mathbf{x}}(t)& =&\left [\begin{array}{cc} \mathbf{A}& 0\\ 0 & - A^{{\ast}} \end{array} \right ]\mathbf{x}(t) + \left [\begin{array}{c} \mathbf{B}\\ - C \end{array} \right ]\mathbf{u}(t)\\ && \\ \mathbf{y}(t) & =& \left [\begin{array}{cc} \mathbf{C}&\mathbf{B} \end{array} \right ]^{{\ast}}\mathbf{x}(t) + (\mathbf{D} + \mathbf{D}^{{\ast}})u(t)\end{array} \right. }$$

(4.43)

Let

$$\displaystyle{\mathcal{A} = \left [\begin{array}{ccc} \mathbf{A} & \mathbf{0} & \mathbf{B}\\ \mathbf{0} & - \mathbf{A} ^{{\ast} }& -\mathbf{C} \\ \mathbf{C}^{{\ast}}& \mathbf{B}^{{\ast}} &\mathbf{D} + \mathbf{D}^{{\ast}} \end{array} \right ]\;\;\;\mathrm{and}\;\;\;\mathcal{E} = \left [\begin{array}{ccc} \mathbf{E}& & \\ &\mathbf{E} ^{{\ast} }& \\ & &\mathbf{0} \end{array} \right ].}$$

The finite spectral zeros of G are the set of all finite complex numbers λ such that

$$\displaystyle{\text{Rank}(\mathcal{A}-\lambda \mathcal{E}) <2n + p,}$$

i.e., the finite generalized eigenvalues $\sigma (\mathcal{A},\mathcal{E})$. The set of spectral zeros is denoted as $\mathcal{S}_{G}$.

Lemma 4.1

If λ is a generalized eigenvalue $\sigma (\mathcal{A}-\lambda \mathcal{E})$ in $\mathcal{S}_{G}$ then $-\bar{\lambda }$ also belongs to $\mathcal{S}_{G}$ , i.e.,

$$\displaystyle{\lambda \in \mathcal{S}_{G} \Rightarrow -\bar{\lambda }\in \mathcal{S}_{G}\quad \text{since}\quad \mathcal{A}\mathbf{q} =\lambda \mathcal{E}\mathbf{q} \Rightarrow \tilde{\mathbf{q}}^{{\ast}}\mathcal{A} = (-\bar{\lambda })\tilde{\mathbf{q}}^{{\ast}}\mathcal{E},}$$

where $\mathbf{q}^{{\ast}} = [\mathbf{x}^{{\ast}},\mathbf{y}^{{\ast}},\mathbf{z}^{{\ast}}]$ is a right eigenvector and $\tilde{\mathbf{q}}^{{\ast}} = [\mathbf{y}^{{\ast}},-\mathbf{x}^{{\ast}},\mathbf{z}^{{\ast}}]$ . Also

$$\displaystyle{\lambda \in \mathcal{S}_{G} \Rightarrow -\bar{\lambda }\in \mathcal{S}_{G}\quad \text{since}\quad \mathbf{r}\mathcal{A} =\lambda \mathbf{r}\mathcal{E}\Rightarrow \mathcal{A}\tilde{\mathbf{r}}^{{\ast}} = (-\bar{\lambda })\mathcal{E}\tilde{\mathbf{r}}^{{\ast}},}$$

where $\mathbf{r}^{{\ast}} = [\mathbf{x1}^{{\ast}},\mathbf{y1}^{{\ast}},\mathbf{z1}^{{\ast}}]$ is a left eigenvector and $\tilde{\mathbf{r}}^{{\ast}} = [-\mathbf{y1}^{{\ast}},\mathbf{x1}^{{\ast}},\mathbf{z1}^{{\ast}}]$ .

Proof

If $\lambda \in \sigma (\mathcal{A}-\lambda \mathcal{E})$ and q is the corresponding eigenvector then

$$\displaystyle{\begin{array}{cc} &\mathcal{A}\mathbf{q} =\lambda \mathcal{E}\mathbf{q}\\ \end{array} }$$

or

$$\displaystyle{\begin{array}{cc} &\left [\begin{array}{ccc} \mathbf{A} & \mathbf{0} & \mathbf{B}\\ \mathbf{0} & - \mathbf{A} ^{{\ast} }& -\mathbf{C} \\ \mathbf{C}^{{\ast}}& \mathbf{B}^{{\ast}} &\mathbf{D} + \mathbf{D}^{{\ast}} \end{array} \right ]\left [\begin{array}{c} \mathbf{x}\\ \mathbf{y} \\ \mathbf{z} \end{array} \right ] =\lambda \left [\begin{array}{ccc} \mathbf{E}& & \\ &\mathbf{E} ^{{\ast} }& \\ & &\mathbf{0} \end{array} \right ]\left [\begin{array}{c} \mathbf{x}\\ \mathbf{y} \\ \mathbf{z} \end{array} \right ]\\ \end{array}}$$

By taking conjugates and changing rows one obtains

$$\displaystyle{\begin{array}{cc} &\left [\begin{array}{ccc} \mathbf{y}^{{\ast}}&-\mathbf{x}^{{\ast}}&\mathbf{z}^{{\ast}} \end{array} \right ]\left [\begin{array}{ccc} \mathbf{A} & \mathbf{0} & \mathbf{B}\\ \mathbf{0} & - \mathbf{A} ^{{\ast} }& -\mathbf{C} \\ \mathbf{C}^{{\ast}}& \mathbf{B}^{{\ast}} &\mathbf{D} + \mathbf{D}^{{\ast}} \end{array} \right ] = -\bar{\lambda }\left [\begin{array}{ccc} \mathbf{y}^{{\ast}}&-\mathbf{x}^{{\ast}}&\mathbf{z}^{{\ast}} \end{array} \right ]\left [\begin{array}{ccc} \mathbf{E}& & \\ &\mathbf{E} ^{{\ast} }& \\ & &\mathbf{0} \end{array} \right ],\;\;\;\mathrm{or} \\ \\ & \tilde{\mathbf{q}}^{{\ast} }\mathcal{A} = -\bar{\lambda }\tilde{\mathbf{q}}^{{\ast}}\mathcal{E}.\end{array} }$$

Now we can conclude that $-\bar{\lambda }\in \mathcal{S}_{G}$ and that $\tilde{\mathbf{q}}^{{\ast}}$ is its corresponding eigenvector. The proof is similar for the left eigenvectors [110]. ■ 

If specified spectral zeros are preserved (interpolated) in the reduced model with $\mathcal{S}_{\hat{G}}$ then a passive reduced model will result. For real systems, $\mathcal{S}_{\hat{G}}$ must include conjugate pairs of spectral zeros. This result is based on Antoulas’ theorem [96]:

Theorem 4.3 (Antoulas)

Suppose $\mathcal{S}_{\hat{G}} \subset \mathcal{S}_{G}$ and also that $\hat{G}(\lambda ) = G(\lambda )$ for all $\lambda \in \mathcal{S}_{\hat{G}}$ and that $\hat{G}$ is a minimal degree rational interpolant of the values of G on the set $\mathcal{S}_{\hat{G}}$ . Then the reduced system $\hat{\sum }$ with transfer function $\hat{G}$ is both stable and passive.

4.4 Passivity Preserving Model Reduction

Theorem 4.3 indicates that Antoulas’s approach [96] preserves passivity for the reduced model when spectral zero interpolation is applied. The interpolation is guaranteed by building the projection matrices using a Krylov subspace method [103, 111]. Antoulas’ method [96] significantly differs from PRIMA [107]. For a detailed comparison between PRIMA and Antoulas’s approach we refer to [105].

In Antoulas’ method it is assumed that the system Σ with transfer function G(s) is passive. Then one defines a set $\mathcal{S}_{1} \subset \mathcal{S}_{\mathbf{G}_{\mathit{stable}}}$ where $\mathcal{S}_{\mathbf{G}_{\mathit{stable}}}$ is the set of stable spectral zeros and one takes $\mathcal{S}_{2} = -\mathcal{S}_{1}$. Antoulas [96] has shown that the reduced system $\hat{\varSigma }$ with transfer function $\hat{\mathbf{G}}(s)$ is passive if the set of interpolation points is $\mathcal{S}_{1} \cup \mathcal{S}_{2}$.

A second approach has been introduced by Sorensen [110], which can be seen as an interpolatory model reduction too. It is based on invariant subspaces. In this method it is not necessary that the spectral zeros (interpolation points) are computed in advance. Sorensen’s approach transfers the model reduction problem into an eigenvalue problem. In this case the eigenvalues are the spectral zeros of the transfer function of the original system. Then the projection matrices are built from a basis for a chosen invariant subspace.

Choosing different spectral zeros gives us different invariant subspaces, which return different reduced models. Although these reduced models are passive, they may not be a good approximation to the original system. So the selection of spectral zeros must guarantee that the reduced model is a good approximation to the original ones.

In large scale problems in which the eigen computation of the resulting highly-structured eigenvalue problem should be done iteratively, all selection criteria can not be satisfied. So the problem has two goals: the first one is to have a good approximation of the original model, the second one is to be suitable as an iterative scheme for large-scale dynamical systems.

4.5 Model Reduction by Projection

We will construct a basis for a selected invariant subspace of the pair $(\mathcal{A},\mathcal{E})$ (Sorensen [110]). Let

$$\displaystyle{\mathcal{A}\mathbf{Q} = \mathcal{E}\mathbf{Q}\mathbf{R}}$$

be a partial real Schur decomposition for the pair $(\mathcal{A},\mathcal{E})$. Then, Q ^∗ Q = I and R is real and quasi-upper triangular. Let $Q = [\mathbf{X}^{{\ast}},\mathbf{Y}^{{\ast}},\mathbf{Z}^{{\ast}}]^{{\ast}}$ be partitioned in accordance with the block structure of $\mathcal{A}$:

$$\displaystyle{ \left [\begin{array}{ccc} \mathbf{A} & \mathbf{0} & \mathbf{B}\\ \mathbf{0} & - \mathbf{A} ^{{\ast} }& -\mathbf{C} \\ \mathbf{C}^{{\ast}}& \mathbf{B}^{{\ast}} &\mathbf{D} + \mathbf{D}^{{\ast}} \end{array} \right ]\left [\begin{array}{c} \mathbf{X}\\ \mathbf{Y} \\ \mathbf{Z} \end{array} \right ] = \left [\begin{array}{ccc} \mathbf{E}& & \\ &\mathbf{E} ^{{\ast} }& \\ & &\mathbf{0} \end{array} \right ]\left [\begin{array}{c} \mathbf{X}\\ \mathbf{Y} \\ \mathbf{Z} \end{array} \right ]\mathbf{R} }$$

$$\displaystyle{ \Rightarrow \left [\begin{array}{ccc} \mathbf{A} & \mathbf{0} & \mathbf{B}\\ \mathbf{0} & - \mathbf{A} ^{{\ast} }& -\mathbf{C} \\ \mathbf{C}^{{\ast}}& \mathbf{B}^{{\ast}} &\mathbf{D} + \mathbf{D}^{{\ast}} \end{array} \right ]\left [\begin{array}{c} \mathbf{X}\\ \mathbf{Y} \\ \mathbf{Z} \end{array} \right ] = \left [\begin{array}{c} \mathbf{EX}\\ \mathbf{E} ^{{\ast} }\mathbf{Y}\\ \mathbf{0} \end{array} \right ]\mathbf{R} }$$

(4.44)

The projection will be constructed from X and Y and the reduced model will be obtained out of these. Here it will be useful to have the following lemma [110].

Lemma 4.2

Suppose that R in  (4.44) satisfies Re(λ) > 0, ∀λ ∈σ( R ). Then $\mathbf{X}^{{\ast}}\mathbf{E}^{{\ast}}\mathbf{Y} = \mathbf{Y}^{{\ast}}\mathbf{E}\mathbf{X}$ is symmetric.

Proof

We start with

$$\displaystyle{ \mathcal{A}\mathbf{Q} = \mathcal{E}\mathbf{Q}\mathbf{R}. }$$

(4.45)

By (4.45) and according to the previous proof we have

$$\displaystyle{ \hat{\mathbf{Q}}^{{\ast}}\mathcal{A} = (-\mathbf{R}^{{\ast}})\hat{\mathbf{Q}}^{{\ast}}\mathcal{E}\quad \text{where}\quad \hat{\mathbf{Q}}^{{\ast}} = \left [\begin{array}{ccc} \mathbf{Y}^{{\ast}}&-\mathbf{X}^{{\ast}}&\mathbf{Z}^{{\ast}} \end{array} \right ], }$$

(4.46)

If we multiply equation (4.45) with $\hat{\mathbf{Q}}^{{\ast}}$ from the left, then we get

$$\displaystyle{ \hat{\mathbf{Q}}^{{\ast}}\mathcal{A}\mathbf{Q} =\hat{ \mathbf{Q}}^{{\ast}}\mathcal{E}\mathbf{Q}\mathbf{R}. }$$

(4.47)

We substitute the right part of equation (4.46) in the left part of equation (4.47), giving

$$\displaystyle\begin{array}{rcl} (-\mathbf{R}^{{\ast}})\hat{\mathbf{Q}}^{{\ast}}\mathcal{E}\mathbf{Q}& =& \hat{\mathbf{Q}}^{{\ast}}\mathcal{E}\mathbf{Q}\mathbf{R} \\ \Rightarrow \quad \mathbf{R}^{{\ast}}\hat{\mathbf{Q}}^{{\ast}}\mathcal{E}\mathbf{Q} +\hat{ \mathbf{Q}}^{{\ast}}\mathcal{E}\mathbf{Q}\mathbf{R}& =& \mathbf{0}. {}\end{array}$$

(4.48)

Here

$$\displaystyle\begin{array}{rcl} \hat{\mathbf{Q}}^{{\ast}}\mathcal{E}\mathbf{Q}& =& \left [\begin{array}{ccc} \mathbf{Y}^{{\ast}}&-\mathbf{X}^{{\ast}}&\mathbf{Z}^{{\ast}} \end{array} \right ]\left [\begin{array}{ccc} \mathbf{E}& & \\ &\mathbf{E} ^{{\ast} }& \\ & &\mathbf{0} \end{array} \right ]\left [\begin{array}{c} \mathbf{X}\\ \mathbf{Y} \\ \mathbf{Z} \end{array} \right ] \\ & =& \mathbf{Y}^{{\ast}}\mathbf{E}\mathbf{X} -\mathbf{X}^{{\ast}}\mathbf{E}^{{\ast}}\mathbf{Y}. {}\end{array}$$

(4.49)

If we substitute (4.49) in (4.48) we obtain

$$\displaystyle{ \mathbf{R}^{{\ast}}(\mathbf{Y}^{{\ast}}\mathbf{E}\mathbf{X} -\mathbf{X}^{{\ast}}\mathbf{E}^{{\ast}}\mathbf{Y}) + (\mathbf{Y}^{{\ast}}\mathbf{E}\mathbf{X} -\mathbf{X}^{{\ast}}\mathbf{E}^{{\ast}}\mathbf{Y})\mathbf{R} = \mathbf{0}. }$$

(4.50)

Therefore the equation (4.50) has the unique solution¹⁹:

$$\displaystyle{\mathbf{Y}^{{\ast}}\mathbf{E}\mathbf{X} -\mathbf{X}^{{\ast}}\mathbf{E}^{{\ast}}\mathbf{Y} = \mathbf{0},}$$

and hence

$$\displaystyle{\mathbf{Y}^{{\ast}}\mathbf{E}\mathbf{X} = \mathbf{X}^{{\ast}}\mathbf{E}^{{\ast}}\mathbf{Y},}$$

which completes the proof. ■ 

For the construction of V and W as projections, we first have to find a basis for an invariant subspace [102] with all eigenvalues of R in the right half-plane.

Let $\mathbf{Q}_{x}\mathbf{S}^{2}\mathbf{Q}_{y}^{{\ast}} = \mathbf{X}^{{\ast}}\mathbf{Y}$ be the SVD of X ^∗ Y and note that $\mathbf{Q}_{y} = \mathbf{Q}_{x}\mathbf{J}$ where J is a signature matrix by virtue of the fact that X ^∗ Y is symmetric.

If S ≥ 0 is nonsingular, put

$$\displaystyle{ \begin{array}{ccc} \mathbf{V} & =& \mathbf{X}\mathbf{Q}_{x}\mathbf{S}^{-1} \\ \mathbf{W}& =&\mathbf{Y}\mathbf{Q}_{y}\mathbf{S}^{-1}. \end{array} }$$

(4.51)

It follows that

$$\displaystyle{\begin{array}{ccc} \mathbf{W}^{{\ast}}\mathbf{V} & =& (\mathbf{Y}\mathbf{Q}_{y}\mathbf{S}^{-1})^{{\ast}}\mathbf{X}\mathbf{Q}_{x}\mathbf{S}^{-1}\\ & & \\ & =& \mathbf{S}^{-{\ast}}\mathbf{Q}_{y}^{{\ast}}\mathbf{Y}^{{\ast}}\mathbf{X}\mathbf{Q}_{x}\mathbf{S}^{-1}\\ & & \\ \mbox{ (include the SVD form of $\mathbf{X}^{{\ast}}\mathbf{Y}$)} & =&\mathbf{S}^{-{\ast}}\mathbf{Q}_{y}^{{\ast}}\mathbf{Q}_{y}(\mathbf{S}^{2})^{{\ast}}\mathbf{Q}_{x}^{{\ast}}\mathbf{Q}_{x}\mathbf{S}^{-1}\\ & & \\ \mbox{ ($\mathbf{Q}_{x}$ and $\mathbf{Q}_{y}$ are unitary matrices)}& =& \mathbf{S}^{-{\ast}}\mathbf{S}^{{\ast}}\mathbf{S}^{{\ast}}\mathbf{S}^{-1} \\ & =& \mathbf{I}. \end{array} }$$

and also we have

$$\displaystyle{\mathbf{V}^{{\ast}}\mathbf{W} = (\mathbf{W}^{{\ast}}\mathbf{V})^{{\ast}} = \mathbf{I}.}$$

Now from the SVD of X ^∗ Y, let

$$\displaystyle{\begin{array}{ccc} \hat{\mathbf{X}}& =& \mathbf{S}(\mathbf{Q}_{x})^{{\ast}} \\ \hat{\mathbf{Y}}& =&\mathbf{S}(\mathbf{Q}_{y})^{{\ast}}, \end{array} }$$

and define

$$\displaystyle{\mathcal{V} = \left [\begin{array}{ccc} \mathbf{V}& \mathbf{0} &\mathbf{0}\\ \mathbf{0} &\mathbf{W} &\mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{I}\\ \end{array} \right ]\quad \text{and}\quad \mathcal{W} = \left [\begin{array}{ccc} \mathbf{W}& \mathbf{0} &\mathbf{0}\\ \mathbf{0} &\mathbf{V} &\mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{I}\\ \end{array} \right ].}$$

It is obvious that $\mathcal{W}^{{\ast}}\mathcal{V} = \mathbf{I}$ and that

$$\displaystyle{\begin{array}{ccc} \mathbf{V}\hat{\mathbf{X}} & =&(\mathbf{X}\mathbf{Q}_{x}\mathbf{S}^{-1})(\mathbf{S}\mathbf{Q}_{x}^{{\ast}}),\\ & & \\ & =& \mathbf{X}\mathbf{Q}_{x}\mathbf{Q}_{x}^{{\ast}},\\ & & \\ (\mathbf{Q}_{x}^{{\ast}}\quad \text{is unitary matrix})& =& \mathbf{X}. \end{array} }$$

Similarly, $\mathbf{W}\hat{\mathbf{Y}} = \mathbf{Y}$, so we have

$$\displaystyle{\left [\begin{array}{c} \mathbf{X}\\ \mathbf{Y} \\ \mathbf{Z} \end{array} \right ] = \left [\begin{array}{ccc} \mathbf{V}& \mathbf{0} &\mathbf{0}\\ \mathbf{0} &\mathbf{W} &\mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{I}\\ \end{array} \right ]\left [\begin{array}{c} \hat{\mathbf{X}}\\ \hat{\mathbf{Y}} \\ \hat{\mathbf{Z}} \end{array} \right ].}$$

Therefore

$$\displaystyle{\hat{\mathcal{A}} = \mathcal{W}^{{\ast}}\mathcal{A}\mathcal{V} = \left [\begin{array}{ccc} \hat{\mathbf{A}} & \mathbf{0} & \hat{\mathbf{B}}\\ \mathbf{0} & -\hat{ \mathbf{A} }^{{\ast} } & -\hat{ \mathbf{C}} \\ \hat{\mathbf{C}}^{{\ast}}& \hat{\mathbf{B}}^{{\ast}} &\mathbf{D} + \mathbf{D}^{{\ast}} \end{array} \right ]\quad \text{and}\quad \hat{\mathcal{E}} = \mathcal{W}^{{\ast}}\mathcal{E}\mathcal{V} = \left [\begin{array}{ccc} \hat{\mathbf{E}}& & \\ &\hat{\mathbf{E} }^{{\ast} }& \\ & &\mathbf{0} \end{array} \right ],}$$

and

$$\displaystyle{\left [\begin{array}{ccc} \hat{\mathbf{A}} & \mathbf{0} & \hat{\mathbf{B}}\\ \mathbf{0} & -\hat{ \mathbf{A} }^{{\ast} }& -\hat{\mathbf{C}} \\ \hat{\mathbf{C}}^{{\ast}}& \hat{\mathbf{B}}^{{\ast}} &\mathbf{D} + \mathbf{D}^{{\ast}} \end{array} \right ]\left [\begin{array}{c} \hat{\mathbf{X}}\\ \hat{\mathbf{Y}} \\ \hat{\mathbf{Z}} \end{array} \right ] = \left [\begin{array}{ccc} \hat{\mathbf{E}}& & \\ &\hat{\mathbf{E} }^{{\ast} }& \\ & &\mathbf{0} \end{array} \right ]\left [\begin{array}{c} \hat{\mathbf{X}}\\ \hat{\mathbf{Y}} \\ \hat{\mathbf{Z}} \end{array} \right ]\mathbf{R},}$$

or

$$\displaystyle{\left [\begin{array}{ccc} \hat{\mathbf{A}} & \mathbf{0} & \hat{\mathbf{B}}\\ \mathbf{0} & -\hat{ \mathbf{A} }^{{\ast} }& -\hat{\mathbf{C}} \\ \hat{\mathbf{C}}^{{\ast}}& \hat{\mathbf{B}}^{{\ast}} &\mathbf{D} + \mathbf{D}^{{\ast}} \end{array} \right ]\left [\begin{array}{c} \hat{\mathbf{X}}\\ \hat{\mathbf{Y}} \\ \hat{\mathbf{Z}} \end{array} \right ] = \left [\begin{array}{c} \hat{\mathbf{E}}\hat{\mathbf{X}}\\ \hat{\mathbf{E} }^{{\ast} }\hat{\mathbf{Y}}\\ \mathbf{0} \end{array} \right ]\mathbf{R}.}$$

where $\hat{\mathbf{A}} = \mathbf{W}^{{\ast}}\mathbf{A}\mathbf{V},\hat{\mathbf{E}} = \mathbf{W}^{{\ast}}\mathbf{E}\mathbf{V},\hat{\mathbf{B}} = \mathbf{W}^{{\ast}}\mathbf{B},$ and $\hat{\mathbf{C}} = \mathbf{V}^{{\ast}}\mathbf{C}$.

This shows that $\mathcal{S}_{\hat{G}} \subseteq \mathcal{S}_{G}$ and since $\mathcal{S}_{\hat{G}} =\sigma (\mathbf{R}) \cup \sigma (\mathbf{-R}^{{\ast}})$ ²⁰ and σ(R) is in the open right half-plane, the reduced model has no spectral zeros on the imaginary axis.

Algorithm 4.7 Sorensen’s Algorithm [110]

The previous result is also valid when S is nonsingular. Now we consider the case S is singular. Beginning with X, Y from (4.44) and with the SVD of X ^∗ Y, where $\mathbf{Q}_{x}\mathbf{S}^{2}\mathbf{Q}_{y} = \mathbf{X}^{{\ast}}\mathbf{Y}$, specify a cut-off tolerance τ _c  ∈ (0, 1) and let j be the largest positive integer such that

$$\displaystyle{\sigma _{j} \geq \tau _{c}\sigma _{1}\quad \quad \text{where}\quad \sigma _{j} = \mathbf{S}(j,j).}$$

Define Q _j  = Q _x (: , 1: j), S _j  = S(1: j,1: j) and then let $(\mathbf{X}_{j})^{I} = \mathbf{Q}_{j}(\mathbf{S}_{j})^{-1}$. Replace $\hat{\mathbf{X}}^{-1} = (\mathbf{X}_{j})^{I}$, V = X(X _j )^I and $\mathbf{W} = -\mathbf{Y}(\mathbf{X}_{j})^{I}$. According to [110], in this way, the reduced system is passive and also the stability of the reduced model is obtained if Z is full rank.

Sorenson’s Algorithm is described in Algorithm 4.7.

4.6 Model Reduction by Projection

We want to reduce the original system ∑ to $\hat{\sum }$ where the complexity k of $\hat{\sum }$ is (much) less than that of ∑ (k ≪ n) (Antoulas [96]). This reduction must preserve both stability and passivity and it must be numerically efficient. Antoulas’ Algorithm is described in Algorithm 4.8.

Algorithm 4.8 Antoulas’s Algorithm [96]

We will look for $\mathbf{V},\mathbf{W} \in \mathbb{R}^{n\times k}$ such that VW ^∗ is a projection with the additional condition W ^∗ V = I _k (recall that P is a projection matrix if P ² = P). So, if we have V and W with $\mathbf{W}^{{\ast}}\mathbf{V} = \mathbf{I}_{k}$, then indeed

$$\displaystyle{(\mathbf{V}\mathbf{W}^{{\ast}})^{2} = \mathbf{V}\mathbf{W}^{{\ast}}.}$$

Given 2k distinct points $s_{1},\cdots \,,s_{2k}$, let

$$\displaystyle\begin{array}{rcl} \tilde{\mathbf{V}}& =& \left [\begin{array}{ccc} (s_{1}\mathbf{I}_{n} -\mathbf{A})^{-1}\mathbf{B}&\cdots &(s_{k}\mathbf{I}_{n} -\mathbf{A})^{-1}\mathbf{B} \end{array} \right ], \\ \tilde{\mathbf{W}}& =& \left [\begin{array}{ccc} (s_{k+1}\mathbf{I}_{n} -\mathbf{A}^{{\ast}})^{-1}\mathbf{C}&\cdots &(s_{2k}\mathbf{I}_{n} -\mathbf{A}^{{\ast}})^{-1}\mathbf{C} \end{array} \right ].{}\end{array}$$

(4.52)

Now take $\mathbf{V} =\tilde{ \mathbf{V}}$ and $\mathbf{W} =\tilde{ \mathbf{W}}(\tilde{\mathbf{V}}^{{\ast}}\tilde{\mathbf{W}})^{-1}$. We define

$$\displaystyle{ \hat{\mathbf{A}} = \mathbf{W}^{{\ast}}\mathbf{A}\mathbf{V},\quad \hat{\mathbf{B}} = \mathbf{W}^{{\ast}}\mathbf{B},\quad \hat{\mathbf{C}} = \mathbf{V}^{{\ast}}\mathbf{C}. }$$

(4.53)

Then we have the following theorem (Antoulas [96])

Proposition 4.1

Assuming that $\mathit{det}(\tilde{\mathbf{W}^{{\ast}}}\tilde{\mathbf{V}})\neq \mathbf{0}$ , the projected system $\hat{\sum }$ , defined by  (4.53) , interpolates the transfer function of ∑ at the points s _i :

$$\displaystyle{\hat{\mathbf{G}}(s_{i}) = \mathbf{G}(s_{i})\quad \quad i = 1,2,\cdots \,,2k.}$$

where s _i are the spectral zeros.

4.7 Numerical Results

In [108] several numerical results are presented for an RLC-circuit that is also found in [96, 110]. The transfer function is a scalar function G(s). The starting point is to compute the spectral zeros (using a generalized eigenvalue method) and then to try to categorize them related to their magnitude, like distance from the real and the imaginary axis in order to have a good match in low or high frequency. The reduced method was obtained by Algorithm 4.8 of Antoulas. A large distance from the real axis results in a good approximation at high frequencies. A large distance from the imaginary axis results in a good approximation at low frequencies. In both situations including the real spectral zeros plays an important role for having a good reduced model at low frequencies.

One should check if a spectral zero also occurs as a pole and as a zero, both, in which case the factors (λ I −A) are singular. These spectra zeros should be left out of the reduction.

In this section we study a circuit which has a descriptor matrix E ≠ I _n . We consider the circuit shown in Fig. 4.16. We assume that all capacitors and inductors have a unit value, $R_{1} = \frac{1} {2}\varOmega$, $R_{2} = \frac{1} {5}\varOmega$, $R_{2k} = \frac{1} {3}\varOmega$, where k = 2, 3, ⋯ , n and $R_{2k+1} = \frac{1} {4}\varOmega$, where k = 1, 2, ⋯ , n.

Fig. 4.16

RLC Circuit of Order 7

Fig. 4.17

Spectral zeros of the original model (+), and spectral zeros of the reduced model (o). For interpolation, the spectral zeros close to the real axis are chosen. All selected spectral zeros are preserved after reduction. The order of the original model is 1003 and it is reduced to 341

Fig. 4.18

Effect of several real spectral zeros, Left: Frequency responses of the original system and reduced model. The spectral zeros close to the real axis are interpolated. Right: Frequency response of the error $\|\varSigma -\hat{\varSigma }\|_{2}$

The order of the original system is 1003 and the selected spectral zeros close to the real axis are shown in Fig. 4.17. In this case, like before, the reduced model has a good match at low and at high frequencies, as shown in Fig. 4.18.

4.8 Conclusion

We have considered two approaches for passive and stable reduction of dynamical systems in circuit simulation, based on the methods by Antoulas [96] and Sorenson [110] that both exploit interpolating spectral zeros. The reduced models preserve passivity and stability. The original system is reduced by projection matrices, which are built via spectral zero interpolation. Different selections of spectral zeros give us different approximations of the original model, which may/may not produce acceptable reduction. We have considered criteria for selecting the spectral zeros and also to approximate the original system well in low and high frequency. When the spectral zeros are chosen close to the real axis, the reduced model matches the original response well for low frequencies. On the other hand, when they are far from the real axis, the reduced model is more accurate for high frequencies. As already shown preserving the real spectral zero plays an important role for having a good reduction in the whole frequency domain, specially in low frequency. It means that one should try to save all the real spectral zeros of the system.

The approaches of Antoulas and Sorensen are equivalent but as Sorensen’s algorithm works directly with eigenvalues and eigenvectors, it is more usable for constructing the projection matrices. For the same reason Sorensen’s approach is more suitable for large scale systems.

5 Passivity Preserving Model Reduction Using the Dominant Spectral Zero Method

The design of integrated circuits has become increasingly complex, thus electromagnetic couplings between components on a chip are no longer negligible.²¹ To verify coupling effects, on-chip interconnections are modeled as RLC circuits and simulated. As these circuits contain millions of electrical components, the underlying dynamical systems have millions of internal variables and cannot be simulated in full dimension. Model order reduction (MOR) aims at approximating the mathematical description of a large scale circuit with a model of smaller dimension, which replaces the original model during verification and speeds up simulation. The reduction method should preserve important properties of the original model (i.e., stability, passivity) and have an efficient, robust implementation, suitable for large-scale applications. RLC circuits describing the interconnect are passive systems, with positive real transfer functions [113, 116], thus reduced models should also be passive. A passive reduced model can be synthesized back into an RLC circuit [113], which is placed instead of the original in the simulation flow. Passive reduced circuits also guarantee stable simulations when integrated with the overall nonlinear macro-model [117, 128, 133] during later simulation stages.

The proposed Dominant Spectral Zero Method (dominant SZM) is a model reduction method which preserves passivity and stability, and is efficiently implemented using the subspace accelerated dominant pole algorithm ( SADPA) [130, 131]. Passivity preservation is ensured via a new approach, that of interpolation at dominant spectral zeros, a subset of spectral zeros of the original model. Dominant SZM reduces automatically all passive systems, including those with formulations unsuitable for PRIMA (first order susceptance-based models for inductive couplings (RCS circuits) [140] or models involving controlled sources, such as vector potential equivalent circuit (VPEC) [139] and partial element equivalent circuit (PEEC) models [136]). In comparison to positive real balanced truncation (PRBT) [129], dominant SZM efficiently handles systems with a possibly singular E matrix [see (4.54)]. Unlike modal approximation (MA) [131, 135] where interpolation is at dominant poles, our method matches the dominant spectral zeros of the original system, guaranteeing passivity.

The remainder of this section is structured as follows. The introduction continues with the mathematical setup of MOR in Sect. 4.4.1, and with a brief description of MOR via spectral zero interpolation in Sect. 4.4.2. Dominant SZM is presented concisely in Sect. 4.4.3.1 (following [125]). It is extended with the concept of dominance at ∞ (Sect. 4.4.3.2), and with an approach for converting the reduced models to circuit representations (Sect. 4.4.3.3). Numerical results follow in Sect. 4.4.4 and the section concludes with Sect. 4.4.5. Algorithmic pseudocode for the dominant SZM – SADPA implementation is given in the Appendix 4.4.6.

5.1 Background on MOR

The model reduction framework involves approximation of an original dynamical system described by a set of differential algebraic equations in the form:

$$\displaystyle{ \mathbf{E}\dot{\mathbf{x}}(t) = \mathbf{A}\mathbf{x}(t) + \mathbf{B}\mathbf{u}(t),\ \mathbf{y}(t)\! =\! \mathbf{C}\mathbf{x}(t) + \mathbf{D}\mathbf{u}(t), }$$

(4.54)

where the entries of x(t) are the system’s internal variables, u(t) is the system input and y(t) is the system output, with dimensions $\mathbf{x}(t) \in \mathbb{R}^{n}$, $\mathbf{u}(t) \in \mathbb{R}^{m}$, $\mathbf{y}(t) \in \mathbb{R}^{p}$. Correspondingly, $\mathbf{E} \in \mathbb{R}^{n\times n}$, $\mathbf{A} \in \mathbb{R}^{n\times n}$, (A, E) is a regular pencil, $\mathbf{B} \in \mathbb{R}^{n\times m}$, $\mathbf{C} \in \mathbb{R}^{p\times n}$, $\mathbf{D} \in \mathbb{R}^{p\times m}$. The original system $\varSigma (\mathbf{E},\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D})$ is stable and passive and has dimension n, usually very large. We seek a reduced order model $\hat{\varSigma }(\hat{\mathbf{E}},\hat{\mathbf{A}},\hat{\mathbf{B}},\hat{\mathbf{C}},\mathbf{D})$, which satisfies: $\hat{\mathbf{E}}\dot{\hat{\mathbf{x}}}(t) = \hat{\mathbf{A}}\hat{\mathbf{x}}(t) + \hat{\mathbf{B}}\mathbf{u}(t)$, $\hat{\mathbf{y}}(t) = \hat{\mathbf{C}}\hat{\mathbf{x}}(t) + \mathbf{D}\mathbf{u}(t)$, where $\hat{\mathbf{x}} \in \mathbb{R}^{k}$, $\hat{\mathbf{E}} \in \mathbb{R}^{k\times k}$, $\hat{\mathbf{A}} \in \mathbb{R}^{k\times k}$, $\hat{\mathbf{B}} \in \mathbb{R}^{k\times m}$, $\hat{\mathbf{C}} \in \mathbb{R}^{p\times k}$, $\mathbf{D} \in \mathbb{R}^{p\times m}$. $\hat{\varSigma }$ is obtained by projecting the internal variables of the original system x onto a subspace $\mathit{ColSpan}(\mathbf{V}) \subset \mathbb{R}^{n\times k}$, along $\mathit{Null}(\mathbf{W}^{{\ast}}) \subset \mathbb{R}^{k\times n}$. The goal is to construct V and W, such that $\hat{\varSigma }$ is stable and passive. Additionally, V and W should be computed efficiently. The reduced matrices are obtained as follows:

$$\displaystyle\begin{array}{rcl} \hat{\mathbf{E}} = \mathbf{W}^{{\ast}}\mathbf{E}\mathbf{V},\ \hat{\mathbf{A}} = \mathbf{W}^{{\ast}}\mathbf{A}\mathbf{V},\ \hat{\mathbf{B}} = \mathbf{W}^{{\ast}}\mathbf{B},\ \hat{\mathbf{C}} = \mathbf{C}\mathbf{V}.& &{}\end{array}$$

(4.55)

5.2 MOR by Spectral Zero Interpolation

We revise the spectral zero interpolation approach for model reduction as proposed in [114, 134]. The ingredient for passivity preservation are the spectral zeros of $\varSigma (\mathbf{E},\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D})$, defined as follows:

Definition 4.5

For system Σ with transfer function: $\mathbf{H}(s):= \mathbf{C}(s\mathbf{E} -\mathbf{A})^{-1}\mathbf{B} + \mathbf{D}$, the spectral zeros are $\mathrm{all}\ s\! \in \! \mathbb{C}\ \mathrm{such\ that}\ \mathbf{H}(s) + \mathbf{H}^{{\ast}}(-s) = 0$, where $\mathbf{H}^{{\ast}}(-s) = \mathbf{B}^{{\ast}}(-s\mathbf{E}^{{\ast}}-\mathbf{A}^{{\ast}})^{-1}\mathbf{C}^{{\ast}}\! +\! \mathbf{D}^{{\ast}}$.

According to [114, 134], model reduction via spectral zero interpolation involves forming rational Krylov subspaces:

$$\displaystyle\begin{array}{rcl} \mathbf{V} = [\!\begin{array}{c} (s_{1}\mathbf{E} -\mathbf{A})^{-1}\mathbf{B},\ \cdots \,,\ (s_{k}\mathbf{E} -\mathbf{A})^{-1}\mathbf{B} \end{array} \!],& & \\ \mathbf{W} = [\!\begin{array}{c} (-s_{1}^{{\ast}}\mathbf{E}^{{\ast}}-\mathbf{A}^{{\ast}})^{-1}\mathbf{C}^{{\ast}},\ \cdots \,,\ (-s_{k}^{{\ast}}\mathbf{E}^{{\ast}}-\mathbf{A}^{{\ast}})^{-1}\mathbf{C}^{{\ast}} \end{array} \!],& &{}\end{array}$$

(4.56)

where $s_{1}\ldots s_{k},-s_{1}^{{\ast}}\ldots - s_{k}^{{\ast}}$ are a subset of the spectral zeros of Σ. By projecting the original system with matrices (4.56) according to (4.55), the reduced $\hat{\varSigma }$ interpolates Σ at the chosen s _i and their mirror images $-s_{i}^{{\ast}}$, i = 1, …, k [113, 114]. Projection matrices V and W insure that the reduced system satisfies the positive real lemma [113, 114, 116, 134], thus passivity is preserved. If in the original system D ≠ 0, the reduced system is strictly passive, and realizable with RLC circuit elements. In Sect. 4.4.3.2 we show one way of obtaining strictly passive reduced systems also when D = 0.

5.3 The Dominant Spectral Zero Method

The new Dominant Spectral Zero Method (dominant SZM) is presented. The spectral zero method [114, 134] is extended with a dominance criterion for selecting finite spectral zeros. These are computed efficiently and automatically using the subspace accelerated dominant pole algorithm (SADPA) [130, 131]. We show in addition how, for certain RLC models, dominant spectral zeros at ∞ can also be easily interpolated.

5.3.1 Dominant Spectral Zeros and Implementation

In [134] it was shown that spectral zeros are solved efficiently from an associated Hamiltonian eigenvalue problem [127, 137]. In [114, 134] however, the selection of spectral zeros was still an open problem. We propose a solution as follows: we extend the concept of dominance from poles [130] to spectral zeros, and adapt the iterative solver SADPA for the computation of dominant spectral zeros. The corresponding invariant subspaces are obtained as a by-product of SADPA, and are used to construct the passivity preserving projection matrices V and W. Essentially, dominant SZM is the SADPA-based implementation of modal approximation for the Hamiltonian system associated with $\mathbf{G}(s) = [\mathbf{H}(s) + \mathbf{H}^{{\ast}}(-s)]^{-1}$. Recalling Def. 4.5, the spectral zeros of Σ are the poles of G(s), with partial fraction expansion: $\mathbf{G}(s) =\mathop{ \sum }_{j=1}^{2n} \frac{\boldsymbol{\mathcal{R}}_{j}} {s-s_{j}},$ where s _i are the poles of G with associated residues $\boldsymbol{\mathcal{R}}_{j}$ [126, 131]. The modal approximate of G(s) is obtained by truncating this sum: $\hat{\mathbf{G}}(s) =\mathop{ \sum }_{j=1}^{2k} \frac{\boldsymbol{\mathcal{R}}_{j}} {s-s_{j}}$. The procedure is outlined next.

• 1. Given $\varSigma (\mathbf{E},\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D})$, construct the associated Hamiltonian system Σ _s , associated with transfer function G(s):

  • a. Σ _s when D​ +​ D ^∗ is invertible:

    $$\displaystyle\begin{array}{rcl} \!\!\!\!\!\!\!\!\!\mathbf{A}_{s}& =& \left (\!\begin{array}{ccc} \mathbf{A}& \mathbf{0} & \mathbf{B}\\ \mathbf{0} & - \mathbf{A} ^{{\ast} }& -\mathbf{C}^{{\ast}} \\ \mathbf{C}& \mathbf{B}^{{\ast}} &\mathbf{D}\! +\! \mathbf{D}^{{\ast}}\end{array} \!\right ),\mathbf{E}_{s} = \left (\!\begin{array}{ccc} \mathbf{E}& \mathbf{0} &\mathbf{0}\\ \mathbf{0} &\mathbf{E} ^{{\ast} }&\mathbf{0}\\ \mathbf{0} & \mathbf{0} &\mathbf{0}\end{array} \!\right ),\mathbf{B}_{s} = \left (\!\begin{array}{c} \mathbf{B}\\ - \mathbf{C}^{{\ast} } \\ \mathbf{0}\end{array} \!\right )\varDelta, \\ \!\!\!\!\!\!\!\!\mathbf{C}_{s}& =& -\varDelta \left (\!\begin{array}{ccc} \mathbf{C}&\ \mathbf{B}^{{\ast}}&\mathbf{0}\end{array} \!\right ),\ \mathbf{D}_{s} =\varDelta = (\mathbf{D}\! +\! \mathbf{D}^{{\ast}})^{-1} {}\end{array}$$

    (4.57)

  • b. Σ _s when D = 0:

    $$\displaystyle\begin{array}{rcl} \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\mathbf{A}_{s} =& \left (\!\begin{array}{ccc} \mathbf{A}& \mathbf{0} & \mathbf{B}\\ \mathbf{0} & - \mathbf{A} ^{{\ast} }&-\mathbf{C}^{{\ast}} \\ \mathbf{C}& \mathbf{B}^{{\ast}} & \mathbf{0}\end{array} \!\right ),\ \mathbf{E}_{s} = \left (\!\begin{array}{ccc} \mathbf{E}& \mathbf{0} &\mathbf{0}\\ \mathbf{0} &\mathbf{E} ^{{\ast} }&\mathbf{0}\\ \mathbf{0} & \mathbf{0} &\mathbf{0}\end{array} \!\right ),\ \mathbf{B}_{s} =& \left (\!\begin{array}{c} \mathbf{B}\\ - \mathbf{C}^{{\ast} } \\ \mathbf{I}\end{array} \!\right ),\ \mathbf{C}_{s} = -\left (\!\begin{array}{ccc} \mathbf{C}&\mathbf{B}^{{\ast}}&\mathbf{I}\end{array} \!\right ) {}\end{array}$$

    (4.58)

• 2. Solve the Hamiltonian eigenvalue problem $(\varLambda,\mathbf{R},\mathbf{L}) =\mathrm{ eig}(\mathbf{A}_{s},\mathbf{E}_{s})$, i.e., $\mathbf{A}_{s}\mathbf{R} = \mathbf{E}_{s}\mathbf{R}\varLambda$, $\mathbf{L}^{{\ast}}\mathbf{A}_{s} = \varLambda \mathbf{L}^{{\ast}}\mathbf{E}_{s}$. $\mathbf{R} = [\mathbf{r}_{1},\ldots,\mathbf{r}_{2n}]$, $\mathbf{L} = [\mathbf{l}_{1},\ldots,\mathbf{l}_{2n}]$ and eigenvalues $\varLambda = \mathrm{diag}(s_{1},\ldots,s_{n},-s_{1}^{{\ast}},\ldots,-s_{n}^{{\ast}})$ are the spectral zeros of Σ.

• 3. Compute residues $\boldsymbol{\mathcal{R}}_{j}$ associated with the stable²² spectral zeros s _j , j = 1… n as follows: $\boldsymbol{\mathcal{R}}_{j} =\gamma _{j}\beta _{j}$, $\gamma _{j} = \mathbf{C}_{s}\mathbf{r}_{j}(\mathbf{l}_{j}^{{\ast}}\mathbf{E}_{s}\mathbf{r}_{j})^{-1}$, $\beta _{j} = \mathbf{l}_{j}^{{\ast}}\mathbf{B}_{s}.$

• 4. Sort spectral zeros descendingly according to dominance criterion $\frac{\|\boldsymbol{\mathcal{R}}_{j}\|} {\vert Re(s_{j})\vert }$ [130, Chapter 3], and reorder right eigenvectors R accordingly.

• 5. Retain the right eigenspace $\hat{\mathbf{R}} = \left [\mathbf{r}_{1},\ \ldots,\ \mathbf{r}_{k}\right ] \in \mathbb{C}^{2n\times k}$, corresponding to the stable k most dominant spectral zeros.

• 6. Construct passivity projection matrices V and W from the rows of $\hat{\mathbf{R}}$: $\mathbf{V} =\hat{ \mathbf{R}}_{[1:n,1:k]}$, $\mathbf{W} =\hat{ \mathbf{R}}_{[n+1:2n,1:k]}$, and reduce Σ according to (4.55).

As explained in [114, 125, 134], by projecting with (4.55), $\hat{\varSigma }$ interpolates the k most dominant spectral zeros of Σ, guaranteeing passivity and stability. For large-scale applications, a full solution to the eigenvalue problem in step 2, followed by the dominant sort 3–4 is computationally unfeasible. Instead, the iterative solver SADPA [130, Chapter 3] is applied with appropriate adaptations for spectral zero computation (see Appendix 4.4.6 for the pseudocode). SADPA implements steps 2–4 efficiently and automatically gives the k most dominant spectral zeros and associated 2n × k right eigenspace $\hat{\mathbf{R}}$. The implementation requires performing an LU factorization of (s _j E −A) at each iteration. The relevant s _j are nevertheless computed automatically in SADPA, which may have several advantages over other methods (see [125] for a more detailed cost analysis).

5.3.2 D = 0 and Dominance at s → ∞

Systems arising in circuit simulation often satisfy D = 0 in (4.54). In this case, the projection (4.55), with W and V obtained in step 6 in Sect. 4.4.3.1, gives a lossless system [125]. This is because W and V only interpolate dominant finite spectral zeros, whereas the original system has spectral zeros at ∞, some of which may be dominant [120]. A strictly passive system (with all poles in the left half plane) can nevertheless be obtained by recovering this dominant behavior. For systems often occurring in circuit simulation this is achieved as follows. Consider the modified nodal analysis (MNA) description of an RLC circuit:

$$\displaystyle\begin{array}{rcl} \mathop{\underbrace{\mathop{\left (\!\begin{array}{ccc} \mathbf{0}&\mathbf{0}& \mathbf{0}\\ \mathbf{0} &\boldsymbol{\mathcal{C}} & \mathbf{0} \\ \mathbf{0}&\mathbf{0}&\boldsymbol{\mathcal{L}} \end{array} \!\right )}}\limits }_{\mathbf{E}}\mathop{ \underbrace{\mathop{ \frac{d} {\mathit{dt}}\,\left (\begin{array}{c} \mathit{v}_{p} \\ \boldsymbol{v}_{i} \\ \boldsymbol{i\!}_{L}\end{array} \!\right )}}\limits _{\dot{\mathbf{x}}}}& +& \mathop{\underbrace{\mathop{\left (\begin{array}{ccc} \boldsymbol{\mathcal{G}}_{11} & \boldsymbol{\mathcal{G}}_{12} & \boldsymbol{\mathcal{E}}_{1} \\ \boldsymbol{\mathcal{G}}_{12}^{{\ast}} & \boldsymbol{\mathcal{G}}_{22} & \boldsymbol{\mathcal{E}}_{2} \\ -\!\boldsymbol{\mathcal{E}}_{1}^{{\ast}}&-\boldsymbol{\mathcal{E}}_{2}^{{\ast}}& \mathbf{0} \end{array} \!\right )}}\limits _{-\!\mathbf{A}}}\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \boldsymbol{v}_{p} \\ \boldsymbol{v}_{i} \\ \boldsymbol{i\!}_{L}\end{array} \!\right )}}\limits _{\mathbf{x}}} =\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \boldsymbol{\mathcal{B}}_{1} \\ \mathbf{0}\\ \mathbf{0} \end{array} \!\right )}}\limits _{\mathbf{B}}} \mathbf{u},{}\end{array}$$

(4.59)

where $\mathbf{u}(t) \in \mathbb{R}^{m}$ are input currents and $\mathbf{y}(t) = \mathbf{C}\mathbf{x} \in \mathbb{R}^{m}$ are output voltages, C = B ^∗. The states are $\mathbf{x}(t) = [\mathbf{v}_{p}(t),\ \mathbf{v}_{i}(t),\ \mathbf{i}_{L}(t)]^{T}$, with $\mathbf{v}_{p}(t) \in \mathbb{R}^{n_{p}}$ the voltages at the input nodes (circuit terminals), $\mathbf{v}_{i}(t) \in \mathbb{R}^{n_{i}}$ the voltages at the internal nodes, and $\mathbf{i}_{L}(t) \in \mathbb{R}^{n_{i_{L}} }$ the currents through the inductors, $n_{p} + n_{i} + n_{i_{L}} = n$. $\boldsymbol{\mathcal{C}}$ and $\boldsymbol{\mathcal{L}}$ are the capacitor and inductor matrix stamps, respectively. With (4.59) it is assumed that no capacitors or inductors are directly connected to the input nodes, thus B ∈ Null(E) and $\mathbf{C}^{{\ast}} \in \mathit{Null}(\mathbf{E}^{{\ast}})$. As B and C are right and left eigenvectors corresponding to dominant poles (and spectral zeros) at ∞ [120], the modified projection matrices are:

$$\displaystyle\begin{array}{rcl} \tilde{\mathbf{W}} = [\mathbf{W},\mathbf{C}^{{\ast}}],\ \tilde{\mathbf{V}} = [\mathbf{W},\mathbf{B}],& &{}\end{array}$$

(4.60)

where W and V are obtained from step 6 in Sect. 4.4.3.1. With (4.60), the finite dominant spectral zeros are interpolated as well as the dominant spectral zeros at ∞, and the reduced system is strictly passive [120]. In [125] two alternatives were proposed for ensuring strict passivity for systems in the more general form (4.54) with D = 0.

5.3.3 Circuit Representation of Reduced Impedance Transfer Function

Reduced models obtained with dominant SZM and other Krylov-type methods ( PRIMA [128], SPRIM [117, 118], SPRIM/IOPOR [115, 138]) are mathematical abstractions of an underlying small RLC circuit. Circuit simulators however can only handle mathematical representations to a limited extent, and reduced models have to be synthesized with RLC circuit elements. We reduce all circuits with respect to the input impedance transfer function (i.e., the inputs are the currents injected into the circuit terminals and the outputs are the voltages measured at the terminals) [123]. After converting the reduced input impedance transfer function to netlist format, the reduced circuit can be driven easily by currents or voltages when simulated. Thus both the input impedance and admittance of an original model can be reproduced (see Sect. 4.4.4). Here, models obtained with dominant SZM are converted to netlist representations using the Foster impedance realization approach [119, 122]. Netlist formats for the SPRIM/IOPOR [115, 117, 138] reduced models are obtained via the RLCSYN unstamping procedure in [123, 138]. With both approaches, the resulting netlists may still contain circuit elements with negative values, nevertheless this does not impede the circuit simulation. Obtaining realistic synthesized models with positive circuit elements only is still an open problem.

5.4 Numerical Results

Two transmission line models are reduced with the proposed dominant spectral zero method and compared with the input-output structure preserving method SPRIM/IOPOR [115, 117, 138]. For both circuits, the circuit simulators²³ yield systems in the form (4.59), thus the dominant SZM projection is (4.60). RLC netlist representations for the reduced models are obtained (see Sect. 4.4.3.3) and simulated with Pstar.

The RLC transmission line with connected voltage controlled current sources (VCCSs) from [125] is reduced with dominant SZM, SPRIM/IOPOR [117, 138] and modal approximation (MA). The transfer function is an input impedance i.e., the circuit is current driven. Matlab simulations of the original and reduced models, as well as the Pstar netlist simulations are shown in Fig. 4.19: the model reduced with Dominant SZM gives the best approximation. Table 4.2 summarizes the reduction: the number of circuit elements and the number of states were reduced significantly and the simulation time was sped up.

In [125], the voltage driven input admittance of an RLC transmission line (consisting of cascaded RLC blocks) was reduced directly as shown in Fig. 4.20. Here we reduce and synthesize the underlying input impedance of the same transmission line (see Figs. 4.21 and 4.22). When driving the reduced netlist by an input voltage during the actual circuit simulation, the same input admittance is obtained as if the input admittance had been reduced directly, as seen in Figs. 4.20 and 4.23. Table 4.3 summarizes the reduction results. Although the reduced mathematical models have the same dimension (k = 23), the reduction effect can only be determined after obtaining the netlist representations. Although the SPRIM/IOPOR synthesized model has fewer states, it has more circuit elements than the dominant SZM model, i.e., the matrix stamp of the model is more dense. This suggests that simulation time is jointly determined by the number of states and the number of circuit elements. Thus for practical purposes it is critical to synthesize reduced models with RLC components.

Fig. 4.19

Original, reduced and synthesized systems: Dominant SZM, SPRIM/IOPOR

Table 4.2 Transmission line with VCCSs: reduction and synthesis summary

Fig. 4.20

Input admittance transfer function: original, synthesized Dominant SZM model

Fig. 4.21

Input impedance transfer function: original and reduced with Dominant SZM

Fig. 4.22

Input impedance transfer function: original, reduced with SPRIM/IOPOR

Fig. 4.23

Input admittance transfer function: original, synthesized SPRIM/IOPOR model

5.5 Concluding Remarks

A novel passivity preserving model reduction method is presented, which is based on interpolation of dominant spectral zeros. Implemented with the SADPA eigenvalue solver, the method computes the partial eigenvalue decomposition of an associated Hamiltonian matrix pair, and constructs the passivity preserving projection. Netlist equivalents for the reduced models are simulated and directions for future work are revealed. Especially in model reduction of multi-terminal circuits, achieving structure preservation, sparsity and small dimensionality simultaneously is an open question. New developments on sparsity-preserving model reduction for multi-terminal RC circuits can be found in [124]. In this context, RLC synthesis with positive circuit elements will also be addressed.

Table 4.3 RLC transmission line: Input impedance reduction and synthesis summary

5.6 Appendix: SADPA for Computing Dominant Spectral Zeros

We outline SADPA for SISO systems; the MIMO implementation is similar and the code for computing dominant poles can be found in [132] or online [130]. The following pseudocode is extracted from [130, Chapter 3] and [131], with efficient modifications to automatically account for the four-fold symmetry ($\lambda,-\lambda ^{{\ast}},\lambda ^{{\ast}},-\lambda$) of spectral zeros. In particular, as soon as a Hamiltonian eigenvalue (spectral zero) λ has converged, we immediately deflate the right/left eigenvectors corresponding to −λ ^∗ as well. It turns out that the right/left eigenvectors corresponding to −λ ^∗ need not be solved for explicitly. Rather, due to the structure of the Hamiltonian matrices [127, 137], they can be written down directly from the already converged left/right eigenvectors for λ, as shown in steps 14–17 of Algorithm 4.9. As for modal approximation [131], [130, Chapter 3] deflation for λ ^∗ and −λ is automatically handled in Algorithm 4.11. To summarize, once the right/left eigenvectors corresponding to an eigenvalue λ have converged, the right/left eigenvectors corresponding to $-\lambda ^{{\ast}},\lambda ^{{\ast}},-\lambda$ are also readily available at no additional computational cost, and can be immediately deflated.

In Algorithm 4.10, the MATLAB qz routine is proposed for solving the small, projected eigenvalue problem in step 1. This reveals the right/left eigenvectors $\tilde{\mathbf{X}},\tilde{\mathbf{V}}$ of the projected pencil directly, however they are neither orthogonal nor bi-G-orthogonal. Thus the normalization in step 3 is needed when computing the residues.

A modified Gram-Schimdt procedure (MGS) is used for orthonormalization. We used the implementation in [130, Algorithm 1.4]. For complete mathematical and algorithmic details of SADPA we refer to [130, Chapter 3] and [131].

Algorithm 4.9 (Λ, R, L) = SADPA$(\mathbf{E}_{h},\mathbf{A}_{h},\mathbf{B}_{h},\mathbf{C}_{h},s_{1},\ldots p_{\mathit{max}},k_{\mathit{min}},k_{\mathit{max}})$

Algorithm 4.10 $(\tilde{\varLambda },\tilde{\mathbf{X}},\tilde{\mathbf{V}})$ = DomSort$(\mathbf{T},\mathbf{G},\mathbf{X},\mathbf{V},\mathbf{B}_{h},\mathbf{C}_{h})$

Algorithm 4.11 $(\varLambda,\mathbf{R},\mathbf{L},\mathbf{X},\mathbf{V},\mathbf{B}_{h},\mathbf{C}_{h}) =\mathrm{ Deflate}(\hat{\lambda },\hat{\mathbf{x}},\hat{\mathbf{v}},\ldots \varLambda,\mathbf{R},\mathbf{L},\hat{\mathbf{X}},\hat{\mathbf{V}},\mathbf{E}_{h},\mathbf{B}_{h},\mathbf{C}_{h})$

Algorithm 4.12 X = Expand($\mathbf{X},\mathbf{R},\mathbf{L},\mathbf{E}_{h},\hat{\mathbf{x}}$)

6 A Framework for Synthesis of Reduced Order Models

The main motivation for this section comes from the need for a general framework for the (re)use of reduced order models in circuit simulation.²⁴ Although many model order reduction methods have been developed and evolved since the 1990s (see for instance [141, 146] for an overview), it is usually less clear how to use these methods efficiently in industrial practice, e.g., in a circuit simulator. One reason can be that the reduced order model does not satisfy certain physical properties, for instance, it may not be stable or passive while the original system is. Failing to preserve these properties is typically inherent to the reduced order method used (or its implementation). Passivity (and stability implicitly) can nowadays be preserved via several methods [142, 151, 157, 166, 169, 173, 174], but none address the practical aspect of (re)using the reduced order models with circuit simulation software (e.g., SPICE [150]). While the original system is available in netlist format, the reduced order model is in general only available in numerical format. Typically, circuit simulators are not prepared for inputs of this form and would require additional software architecture to handle them. In contrast, a reduced model in netlist representation could be easily coupled to bigger systems and simulated.

Synthesis is the realization step needed to map the reduced order model into a netlist consisting of electrical circuit components [154, 170]. In [148] it was shown that passive systems (with positive real transfer functions) can be synthesized with positive R,L,C elements and transformers. Later developments [147] propose a method to circumvent the introduction of transformers, however the resulting realization is non-minimal (i.e., the number of electrical components generated during synthesis is too large). Allowing for possibly negative R, L, C values, other methods have been proposed via e.g. direct stamping [163, 166] or full realization [155, 167]. These mostly model the input/output connections of the reduced model with controlled sources.

In this section we consider two synthesis methods that do not involve controlled sources: (1) Foster synthesis [154], where the realization is done via the system’s transfer function and (2) RLCYSN synthesis by unstamping [176], which exploits input-output structure preservation in the reduced system matrices [provided that the original system matrices are written in modified nodal analysis (MNA) representation]. The focus of this section is on structure preservation and RLCSYN, especially because synthesis by unstamping is simple to implement for both SISO and MIMO systems. Strengthening the result of [176], we give a simple procedure to reduce either current- or voltage-driven circuits directly in impedance form by removing all the sources. Such an impedance-based reduction enables synthesis without controlled sources. The reduced order model is available as a netlist, making it suitable for simulation and reuse in other designs. Similar software [149] is commercially available.

The material in this section is organized as follows. A brief mathematical formulation of model order reduction is given in Sect. 4.5.1. The Foster synthesis is presented in Sect. 4.5.2. In Sect. 4.5.3 we focus on reduction and synthesis with structure (and input/output) preservation. Section 4.5.3.1 describes the procedure to convert admittance models to impedance form, so that synthesized models are easily (re)used in simulation. Based on [176], Sect. 4.5.3.2 is an outline of SPRIM/IOPOR reduction and RLCSYN synthesis. Examples follow in Sect. 4.5.4, and Sect. 4.5.5 concludes.

6.1 Problem Formulation

In this section the dynamical systems Σ(A, E, B, C, D) are of the form $\mathbf{E}\dot{\mathbf{x}}(t) = \mathbf{A}\mathbf{x}(t) + \mathbf{B}\mathbf{u}(t)$, $\mathbf{y}(t) = \mathbf{C}\mathbf{x}(t) + \mathbf{D}\mathbf{u}(t),$ where $\mathbf{A},\mathbf{E} \in \mathbb{R}^{n\times n}$, E may be singular but the pencil (A, E) is regular, $\mathbf{B} \in \mathbb{R}^{n\times m}$, $\mathbf{C} \in \mathbb{R}^{p\times n}$, $\mathbf{x}(t) \in \mathbb{R}^{n}$, and $\mathbf{u}(t) \in \mathbb{R}^{m}$, $\mathbf{y}(t) \in \mathbb{R}^{p}$, $\mathbf{D} \in \mathbb{R}^{p\times m}$. If m, p > 1, the system is called multiple-input multiple-output (MIMO), otherwise it is called single-input single-output (SISO). The frequency domain transfer function is defined as:

$\mathbf{H}(s) = \mathbf{C}(s\mathbf{E} -\mathbf{A})^{-1}\mathbf{B} + \mathbf{D}.$

For systems in MNA form arising in circuit simulation see Sect. 4.5.3.

The model order reduction problem is to find, given an n-th order (descriptor) dynamical system, a k-th order system: $\tilde{\mathbf{E}}\dot{\tilde{\mathbf{x}}}(t) =\tilde{ \mathbf{A}}\tilde{\mathbf{x}}(t) +\tilde{ \mathbf{B}}\mathbf{u}(t)$, $\tilde{\mathbf{y}}(t) =\tilde{ \mathbf{C}}\tilde{\mathbf{x}}(t) + \mathbf{D}\mathbf{u}(t)$ where k < n, and $\tilde{\mathbf{E}},\tilde{\mathbf{A}} \in \mathbb{R}^{k\times k}$, $\tilde{\mathbf{B}} \in \mathbb{R}^{k\times m}$, $\tilde{\mathbf{C}} \in \mathbb{R}^{p\times k}$, $\tilde{\mathbf{x}}(t) \in \mathbb{R}^{k}$, $\mathbf{u}(t) \in \mathbb{R}^{m}$, $\tilde{\mathbf{y}}(t) \in \mathbb{R}^{p}$, and $\mathbf{D} \in \mathbb{R}^{p\times m}$. The number of inputs and outputs is the same as for the original system, and the corresponding transfer function becomes:

$\tilde{\mathbf{H}}(s) =\tilde{ \mathbf{C}}(s\tilde{\mathbf{E}} -\tilde{\mathbf{A}})^{-1}\tilde{\mathbf{B}} + \mathbf{D}.$

For an overview of model order reduction methods, see [141, 145, 146, 172]. Projection based model order reduction methods construct a reduced order model via Petrov-Galerkin projection:

$$\displaystyle{ \tilde{\varSigma }(\tilde{\mathbf{E}},\tilde{\mathbf{A}},\tilde{\mathbf{B}},\tilde{\mathbf{C}},\mathbf{D}) \equiv (\mathbf{W}^{{\ast}}\mathbf{E}\mathbf{V},\mathbf{W}^{{\ast}}\mathbf{A}\mathbf{V},\mathbf{W}^{{\ast}}\mathbf{B},\mathbf{V}^{{\ast}}\mathbf{C},\mathbf{D}), }$$

(4.61)

where $\mathbf{V},\mathbf{W} \in \mathbb{R}^{n\times k}$ are matrices whose k < n columns form bases for relevant subspaces of the state-space. There are several projection methods, that differ in the way the matrices V and W are chosen. These also determine which properties are preserved after reduction. Some stability preserving methods are: modal approximation [171], Poor Man’s TBR [168]. Among moment matching [152] methods, the following preserve passivity: PRIMA [166], SPRIM [151], spectral zero interpolation, [142, 157, 161, 173]. From the balancing methods, balanced truncation [144] preserves stability, and positive real balanced truncation [169, 174] preserves passivity.

6.2 Foster Synthesis of Rational Transfer Functions

This section describes the Foster synthesis method, which was developed in the 1930s by Foster and Cauer [154] and involves realization based on the system’s transfer function. The Foster approach can be used to realize any reduced order model that is computed by standard projection based model order reduction techniques. Realizations will be described in terms of SISO impedances (Z-parameters). For equivalent realizations in terms of admittances (Y -parameters), see for instance [154, 175]. Given the reduced system (4.61) consider the partial fraction expansion [162] of its transfer function:

$$\displaystyle{ \tilde{\mathbf{H}}(s) =\sum _{ i=1}^{k} \frac{\tilde{r}_{i}} {s -\tilde{ p}_{i}} + \mathbf{D}, }$$

(4.62)

The residues are $\tilde{r}_{i} = \frac{(\tilde{\mathbf{C}}\tilde{\mathbf{x}}_{i})(\tilde{\mathbf{y}}_{i}^{{\ast}}\tilde{\mathbf{B}})} {\tilde{\mathbf{y}}_{i}^{{\ast}}\tilde{\mathbf{E}}\tilde{\mathbf{x}}_{i}}$ and the poles are $\tilde{p}_{i}$. An eigentriplet $(\tilde{p}_{i},\tilde{\mathbf{x}}_{i},\tilde{\mathbf{y}}_{i})$ is composed of an eigenvalue $\tilde{p}_{i}$ of $(\tilde{\mathbf{A}},\tilde{\mathbf{E}})$ and the corresponding right and left eigenvectors $\tilde{\mathbf{x}}_{i},\tilde{\mathbf{y}}_{i} \in \mathbb{C}^{k}$. The expansion (4.62) consists of basic summands of the form:

$$\displaystyle{ Z(s) = r_{1} + \frac{r_{2}} {s - p_{2}} + \frac{r_{3}} {s} + \left ( \frac{r_{4}} {s - p_{4}} + \frac{\bar{r}_{4}} {s -\bar{ p}_{4}}\right ) + sr_{6} + \left ( \frac{r_{7}} {s - p_{7}} + \frac{r_{7}} {s -\bar{ p}_{7}}\right ), }$$

(4.63)

where for completeness we can assume that any kind of poles may appear, i.e., either purely real, purely imaginary, in complex conjugate pairs, at ∞ or at 0 (see also Table 4.4). The Foster realization converts each term in (4.63) into the corresponding circuit block with R, L, C components, and connects these blocks in series in the final netlist. This is shown in Fig. 4.24. Note that any reordering of the circuit blocks in the realization of (4.63) in Fig. 4.24 still is a realization of (4.63). The values for the circuit components in Fig. 4.24 are determined according to Table 4.4.

Table 4.4 Circuit element values for Fig. 4.24 for the Foster impedance realization of (4.63)

Fig. 4.24

Realization of a general impedance transfer function as a series RLC circuit

The realization in netlist form can be implemented in any language such as SPICE [150], so that it can be reused and combined with other circuits as well. The advantages of Foster synthesis are: (1) its straightforward implementation for single-input-single-output (SISO) transfer functions, via either the impedance or the admittance transfer function, (2) for purely RC or RL circuits, netlists obtained from reduction via modal approximation [171] are guaranteed to have positive RC or RL values respectively [158]. The main disadvantage is that for multi-input-multi-output transfer functions, finding the Foster realization (see for instance [175]) is cumbersome and may also give dense reduced netlists (i.e., all nodes are interconnected). This is because the Foster synthesis of a k-dimensional reduced system with p terminals, will generally yield O(p ² k) circuit elements. A method based on partitioning of an RLC circuit is found in [164]. The method produces a positive-valued, passive and stable reduced RLC circuit.

6.3 Structure Preservation and Synthesis by Unstamping

This section describes the second synthesis approach, which is based on unstamping the reduced matrix data into an RLC netlist and is denoted by RLCSYN [176]. It is suitable for obtaining netlist representations for models reduced via methods that preserve the MNA structure and the circuit terminals, such as the input-output structure preserving method SPRIM/IOPOR [176]. The strength of the result in [176] is that the input/output connectivity is synthesized after reduction without controlled sources, provided that the system is in impedance form (i.e., inputs are currents injected into the circuit terminals, and outputs are voltages measured at the terminals). Here, we interpret the input-output preservation as preserving the external nodes²⁵ of the original model during reduction. This way the reduced netlist can easily be coupled to other circuitry in place of the original netlist, and (re)using the reduced model in simulation becomes straightforward. The main drawback is that, when the reduced system matrices are dense and the number of terminals is large [O(10³)], the netlist obtained from RLCSYN will be dense. For a k dimensional reduced network with p terminals, the RLCSYN synthesized netlist will generally have $O(p^{2}k^{2})$ circuit elements. The density of the reduced netlist however is not a result of the synthesis procedure, but a consequence of the fact that the reduced system matrices are dense. Developments for sparsity preserving model reduction for multi-terminal circuits can be found in [160], where sparse netlists are obtained by synthesizing sparse reduced models via RLCSYN.

First, we motivate reduction and synthesis in impedance form, and show how it also applies for systems that are originally in admittance form. Then we explain model reduction via SPRIM/IOPOR, followed by RLCSYN synthesis.

6.3.1 A Simple Admittance to Impedance Conversion

In [176] it was shown how SPRIM/IOPOR preserves the structure of the input/output connectivity when the original model is in impedance form, allowing for synthesis via RLCSYN without controlled sources. The emerging question is: How to ensure synthesis without controlled sources, if the original model is in admittance form (i.e., it is voltage driven)? We show that reduction and synthesis via the input impedance transfer function is possible by removing any voltage sources from the original circuit a priori and re-inserting them in the reduced netlist if needed.

To this end, consider the modified nodal analysis (MNA) description of an input admittance ²⁶ type RLC circuit, driven by voltage sources:

$$\displaystyle\begin{array}{rcl} \mathop{\underbrace{\mathop{\left (\!\begin{array}{ccc} \boldsymbol{\mathcal{C}}&\mathbf{0}& \mathbf{0}\\ \mathbf{0} &\mathbf{0} & \mathbf{0} \\ \mathbf{0}&\mathbf{0}&\boldsymbol{\mathcal{L}} \end{array} \!\right )}}\limits }_{\mathbf{E}_{Y }}\mathop{ \underbrace{\mathop{ \frac{d} {\mathit{dt}}\,\left (\!\begin{array}{c} \boldsymbol{v}(t) \\ \boldsymbol{i\!}_{S}(t) \\ \boldsymbol{i\!}_{L}(t) \end{array} \!\right )}}\limits _{\dot{\mathbf{x}}_{Y }}}& +& \mathop{\underbrace{\mathop{\left (\!\begin{array}{ccc} \boldsymbol{\mathcal{G}} &\boldsymbol{\mathcal{E}}_{v}&\boldsymbol{\mathcal{E}}_{l} \\ -\!\boldsymbol{\mathcal{E}}_{v}^{{\ast}}& \mathbf{0} & \mathbf{0} \\ -\!\boldsymbol{\mathcal{E}}_{l}^{{\ast}}& \mathbf{0} & \mathbf{0} \end{array} \!\right )}}\limits _{-\!\mathbf{A}_{Y }}}\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \boldsymbol{v}(t) \\ \boldsymbol{i\!}_{S}(t) \\ \boldsymbol{i\!}_{L}(t) \end{array} \!\right )}}\limits _{\mathbf{x}_{Y }}} =\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \mathbf{0}\\ \boldsymbol{\mathcal{B}} \\ \mathbf{0} \end{array} \!\right )}}\limits _{\mathbf{B}_{Y }}} \mathbf{u}(t),{}\end{array}$$

(4.64)

where $\mathbf{u}(t) \in \mathbb{R}^{n_{1}}$ are input voltages and $\mathbf{y}(t) = \mathbf{C}_{Y }\mathbf{x}(t) \in \mathbb{R}^{n_{1}}$ are output currents, $\mathbf{C}_{Y } = \mathbf{B}_{Y }^{{\ast}}$. The states are $\mathbf{x}_{Y }(t) = [\mathbf{v}(t),\ \mathbf{i}_{S}(t),\ \mathbf{i}_{L}(t)]^{T}$, with $\mathbf{v}(t) \in \mathbb{R}^{n_{v}}$ the node voltages, $\mathbf{i}_{S}(t) \in \mathbb{R}^{n_{1}}$ the currents through the voltage sources, and $\mathbf{i}_{L}(t) \in \mathbb{R}^{n_{l}}$ the currents through the inductors, $n_{v} + n_{1} + n_{l} = n$. The $n_{v} = n_{1} + n_{2}$ node voltages correspond to the n ₁ external nodes (i.e., the number of inputs/terminals) and the n ₂ internal nodes.²⁷ Assuming without loss of generality that (4.64) is permuted such that the first n ₁ nodes are the external nodes, we have:

$\mathbf{v}_{1:n_{1}}(t) = \mathbf{u}(t).$

The dimensions of the underlying matrices are:

$\boldsymbol{\mathcal{C}}\in \mathbb{C}^{n_{v}\times n_{v}},\ \boldsymbol{\mathcal{G}}\in \mathbb{C}^{n_{v}\times n_{v}},\ \boldsymbol{\mathcal{E}}_{v} \in \mathbb{C}^{n_{v}\times n_{1}},\ \boldsymbol{\mathcal{L}}\in \mathbb{C}^{n_{l}\times n_{l}},\ \boldsymbol{\mathcal{E}}_{l} \in \mathbb{C}^{n_{v}\times n_{l}},\ \boldsymbol{\mathcal{B}}\in \mathbb{C}^{n_{1}\times n_{1}}.$

Recalling that $\mathbf{v}_{1:n_{1}}(t) = \mathbf{u}(t)$, the following holds:

$$\displaystyle\begin{array}{rcl} \boldsymbol{\mathcal{E}}_{v} = \left (\!\begin{array}{c} \boldsymbol{\mathcal{B}}_{v} \\ \mathbf{0}_{n_{2}\times n_{1}} \end{array} \!\right ) \in \mathbb{C}^{n_{v}\times n_{1} },\ \ \boldsymbol{\mathcal{B}}_{v} \in \mathbb{C}^{n_{1}\times n_{1} },\ \ \boldsymbol{\mathcal{B}} = -\boldsymbol{\mathcal{B}}_{v}.& &{}\end{array}$$

(4.65)

We derive the first order impedance-type system associated with (4.64). Note that by definition, i _S (t) flows out of the circuit terminals into the voltage source (i.e., from the + to the − terminal of the voltage source, see also [166, Figure 3] [158]). We can define new input currents as the currents flowing into the circuit terminals: $\mathbf{i}_{\mathit{in}}(t) = -\!\mathbf{i}_{S}(t)$. Since $\mathbf{u}(t) = \mathbf{v}_{1:n_{1}}(t)$ are the terminal voltages, they describe the new output equations, and it is straightforward to rewrite (4.64) in the impedance form:

$$\displaystyle\begin{array}{rcl} \left \{\begin{array}{rcl} \mathop{\underbrace{\mathop{\left (\!\begin{array}{cc} \boldsymbol{\mathcal{C}}&\mathbf{0}\\ \mathbf{0} &\boldsymbol{\mathcal{L}} \end{array} \!\right )}}\limits _{\mathbf{E}}}\mathop{ \underbrace{\mathop{ \frac{d} {\mathit{dt}}\,\left (\!\begin{array}{c} \boldsymbol{v}(t) \\ \boldsymbol{i\!}_{L}(t) \end{array} \!\right )}}\limits _{\dot{\mathbf{x}}}}\!& \!+\! &\!\mathop{\underbrace{\mathop{\left (\!\begin{array}{cc} \boldsymbol{\mathcal{G}} &\boldsymbol{\mathcal{E}}_{l} \\ -\!\boldsymbol{\mathcal{E}}_{l}^{{\ast}}&\mathbf{0} \end{array} \!\right )}}\limits _{-\mathbf{A}}}\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \boldsymbol{v}(t)\\ \boldsymbol{i\!}_{ L}(t) \end{array} \!\right )}}\limits _{\mathbf{x}}} =\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \boldsymbol{\mathcal{E}}_{v}\\ \mathbf{0}\end{array} \!\right )}}\limits _{\mathbf{B}}} \mathbf{i}_{\mathit{in}}(t) \\ \mathop{\underbrace{\mathop{\left (\!\begin{array}{cc} \boldsymbol{\mathcal{E}}_{v}^{{\ast}}&\mathbf{0} \end{array} \!\right )}}\limits _{\mathbf{C}}}\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \boldsymbol{v}(t)\\ \boldsymbol{i\!}_{ L}(t) \end{array} \!\right )}}\limits _{\mathbf{x}}}\!&\! =\!&\!\mathbf{y}(t)\ =\ \boldsymbol{\mathcal{B}}_{v}\mathbf{v}_{1:n_{1}}(t),\ \ \ \ \ \boldsymbol{\mathcal{E}}_{v}^{{\ast}} = \left (\!\begin{array}{cc} \boldsymbol{\mathcal{B}}_{v}^{{\ast}}&\mathbf{0}_{ n_{1}\times n_{2}} \end{array} \!\right )\end{array} \right.& &{}\end{array}$$

(4.66)

where B describes the new input incidence matrix corresponding the input currents, i _in . The new output incidence matrix is C, corresponding to the voltages at the circuit terminals. We emphasize that (4.66) has fewer unknowns than (4.64), since the currents i _S have been eliminated. The transfer function associated to (4.66) is an input impedance: $\mathbf{H}(s) = \frac{\mathbf{y}(s)} {\mathbf{i}_{\mathit{in}}(s)}$. In Sect. 4.5.3.2 we explain how to obtain an impedance type reduced order model in input/output structure preserved form:

$$\displaystyle\begin{array}{rcl} \left \{\begin{array}{rcl} \mathop{\underbrace{\mathop{\left (\!\begin{array}{cc} \tilde{\boldsymbol{\mathcal{C}}}&\mathbf{0}\\ \mathbf{0} &\tilde{\boldsymbol{\mathcal{L}}} \end{array} \!\right )}}\limits _{\tilde{\mathbf{E}}}}\mathop{ \underbrace{\mathop{ \frac{d} {\mathit{dt}}\,\left (\begin{array}{c} \tilde{\boldsymbol{v}}(t) \\ \tilde{\boldsymbol{i\!}}_{L}(t) \end{array} \!\right )}}\limits _{\dot{\tilde{\mathbf{x}}}}}\!& \!+\! &\!\mathop{\underbrace{\mathop{\left (\!\begin{array}{cc} \tilde{\boldsymbol{\mathcal{G}}} &\tilde{\boldsymbol{\mathcal{E}}}_{l} \\ -\tilde{\!\boldsymbol{\mathcal{E}}}_{l}^{{\ast}}&\mathbf{0} \end{array} \!\right )}}\limits _{-\!\tilde{\mathbf{A}}}}\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \tilde{\boldsymbol{v}}(t)\\ \tilde{\boldsymbol{i\!}}_{ L}(t) \end{array} \!\right )}}\limits _{\tilde{\mathbf{x}}}} =\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \tilde{\boldsymbol{\mathcal{E}}}_{v}\\ \mathbf{0}\end{array} \!\right )}}\limits _{\tilde{\mathbf{B}}}} \mathbf{i}_{\mathit{in}}(t) \\ \mathop{\underbrace{\mathop{\left (\!\begin{array}{cc} \tilde{\boldsymbol{\mathcal{E}}}_{v}^{{\ast}}&\mathbf{0} \end{array} \!\right )}}\limits _{\tilde{\mathbf{C}}}}\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \tilde{\boldsymbol{v}}(t)\\ \tilde{\boldsymbol{i\!}}_{ L}(t) \end{array} \!\right )}}\limits _{\tilde{\mathbf{x}}}}\!&\! =\!&\!\mathbf{y}(t)\ =\ \boldsymbol{\mathcal{B}}_{v}\mathbf{v}_{1:n_{1}}(t),\ \ \tilde{\boldsymbol{\mathcal{E}}}_{v}^{{\ast}} = \left (\!\begin{array}{cc} \boldsymbol{\mathcal{B}}_{v}^{{\ast}}&\mathbf{0}_{ n_{1}\times k_{2}} \end{array} \!\right )\end{array} \right.& &{}\end{array}$$

(4.67)

where $\tilde{\boldsymbol{\mathcal{C}}}$, $\tilde{\boldsymbol{\mathcal{L}}}$, $\tilde{\boldsymbol{\mathcal{G}}}$, $\tilde{\boldsymbol{\mathcal{E}}}_{v}$ are the reduced MNA matrices, and the reduced input impedance transfer function is: $\tilde{\mathbf{H}}(s) = \frac{\tilde{\mathbf{y}}(s)} {\mathbf{i}_{\mathit{in}}(s)}.$ Due to the input/output preservation, the circuit terminals are easily preserved in the reduced model (4.67). The simple example in Sect. 4.5.4.1 illustrates the procedure just described.

It turns out that after reduction and synthesis, the reduced model (4.67) can still be used as a voltage driven admittance block in simulation. This is shown next. We can rewrite the second equation in (4.67) as: $\left (\!\begin{array}{ccc} -\!\tilde{\boldsymbol{\mathcal{E}}}_{v}^{{\ast}}&\mathbf{0}&\mathbf{0} \end{array} \!\right )\left (\!\begin{array}{ccc} \tilde{\mathbf{v}}(t)^{\!T\!}&\ \tilde{\mathbf{i}}_{S}(t)^{\!T\!}&\ \tilde{\mathbf{i}}_{L}(t)^{\!T\!} \end{array} \!\right )^{\!T\!} = \boldsymbol{\mathcal{B}}\mathbf{u}(t)$. This result together with $\mathbf{i}_{\mathit{in}}(t) = -\!\mathbf{i}_{S}(t)$, reveals that (4.67) can be rewritten as:

$$\displaystyle\begin{array}{rcl} \mathop{\underbrace{\mathop{\left (\!\begin{array}{ccc} \tilde{\boldsymbol{\mathcal{C}}}&\mathbf{0}& \mathbf{0}\\ \mathbf{0} &\mathbf{0} & \mathbf{0} \\ \mathbf{0}&\mathbf{0}&\tilde{\boldsymbol{\mathcal{L}}} \end{array} \!\right )}}\limits _{\tilde{\mathbf{E}}_{Y }}}\mathop{ \underbrace{\mathop{ \frac{d} {\mathit{dt}}\,\left (\!\begin{array}{c} \tilde{\boldsymbol{v}}(t) \\ \boldsymbol{i\!}_{S}(t) \\ \tilde{\boldsymbol{i\!}}_{L}(t) \end{array} \!\right )}}\limits _{\dot{\tilde{\mathbf{x}}}_{Y }}}& +& \mathop{\underbrace{\mathop{\left (\!\begin{array}{ccc} \tilde{\boldsymbol{\mathcal{G}}} &\tilde{\boldsymbol{\mathcal{E}}}_{v}&\tilde{\boldsymbol{\mathcal{E}}}_{l} \\ -\!\tilde{\boldsymbol{\mathcal{E}}}_{v}^{{\ast}}& \mathbf{0} & \mathbf{0} \\ -\!\tilde{\boldsymbol{\mathcal{E}}}_{l}^{{\ast}}& \mathbf{0} & \mathbf{0} \end{array} \!\right )}}\limits _{-\!\tilde{\mathbf{A}}_{Y }}}\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \tilde{\boldsymbol{v}}(t) \\ \boldsymbol{i\!}_{S}(t) \\ \tilde{\boldsymbol{i\!}}_{L}(t) \end{array} \!\right )}}\limits _{\tilde{\mathbf{x}}_{Y }}} =\mathop{ \underbrace{\mathop{\left (\!\begin{array}{c} \mathbf{0}\\ \boldsymbol{\mathcal{B}} \\ \mathbf{0} \end{array} \!\right )}}\limits _{\tilde{\mathbf{B}}_{Y }}} \mathbf{u}(t),{}\end{array}$$

(4.68)

which has the same structure as the original admittance model (4.64). Conceptually one could have reduced system (4.64) directly via the input admittance. In that case, synthesis by unstamping via RLCSYN [176] would have required controlled sources [155] to model the connections at the circuit terminals. As shown above, this is avoided by: applying the simple admittance-to-impedance conversion (4.64) to (4.66), reducing (4.66) to (4.67), and finally reinserting voltage sources after synthesis [if the input-output structure preserved admittance reduced admittance (4.68) is needed]. Being only a pre- and post-processing step, the proposed voltage-source removal and re-insertion can be applied irrespective of the model reduction algorithm used. For ease of understanding we relate it here to model reduction via SPRIM/IOPOR.

6.3.2 I/O Structure Preserving Reduction and RLCSYN Synthesis

The reduced input impedance model (4.67) is obtained via the input-output structure preserving SPRIM/IOPOR projection [176] as follows. Let $\mathbf{V} = \left (\mathbf{V}_{1}^{T},\mathbf{V}_{2}^{T},\mathbf{V}_{3}^{T}\right )^{T} \in \mathbb{C}^{((n_{1}+n_{2}+n_{l})\times k)}$ be the projection matrix obtained with PRIMA [166], where $\mathbf{V}_{1} \in \mathbb{C}^{(n_{1}\times k)}$, $\mathbf{V}_{2} \in \mathbb{C}^{(n_{2}\times k)}$, $\mathbf{V}_{3} \in \mathbb{C}^{(n_{l}\times k)}$, k ≥ n ₁, i = 1…3. After appropriate orthonormalization (e.g., via Modified Gram-Schmidt [171, Chapter 1]), we obtain: $\tilde{\mathbf{V}}_{i} =\mathrm{ orth}(\mathbf{V}_{i}) \in \mathbb{C}^{n_{i}\times k_{i}}$,k _i  ≤ k. The SPRIM [151] block structure preserving projection is: $\tilde{\mathbf{V}} =\mathrm{ blkdiag}\left (\!\tilde{\mathbf{V}}_{1},\tilde{\mathbf{V}}_{2},\tilde{\mathbf{V}}_{3}\!\right ) \in \mathbb{C}^{n\times (k_{1}+k_{2}+k_{3})},$ which does not yet preserve the structure of the input and output matrices. The input-output structure preserving SPRIM/IOPOR [176] projection is $\tilde{\mathbf{W}} = \left (\!\begin{array}{cc} \mathbf{W}& \mathbf{0}\\ \mathbf{0} &\tilde{\mathbf{V} } _{3} \end{array} \!\right ) \in \mathbb{C}^{n\times (n_{1}+k_{2}+k_{3})}$ where:

$$\displaystyle\begin{array}{rcl} \mathbf{W} = \left (\!\begin{array}{cc} \mathbf{I}_{n_{1}\times n_{1}} & \mathbf{0} \\ \mathbf{0} &\tilde{\mathbf{V}}_{2} \end{array} \!\right ) \in \mathbb{C}^{(n_{1}+n_{2})\times (n_{1}+k_{2})}.& &{}\end{array}$$

(4.69)

Recalling (4.65), we obtain the reduced system matrices in (4.67): $\tilde{\boldsymbol{\mathcal{C}}} = \mathbf{W}^{{\ast}}\boldsymbol{\mathcal{C}}\mathbf{W}$, $\tilde{\boldsymbol{\mathcal{G}}} = \mathbf{W}^{{\ast}}\boldsymbol{\mathcal{G}}\mathbf{W}$, $\tilde{\boldsymbol{\mathcal{L}}} = \tilde{\mathbf{V}}_{3}^{{\ast}}\boldsymbol{\mathcal{L}}\tilde{\mathbf{V}}_{3}$, $\tilde{\boldsymbol{\mathcal{E}}}_{l} = \mathbf{W}^{{\ast}}\boldsymbol{\mathcal{E}}_{l}\tilde{\mathbf{V}}_{3}$, $\tilde{\boldsymbol{\mathcal{E}}}_{v} = \mathbf{W}^{{\ast}}\boldsymbol{\mathcal{E}}_{v} = \left (\!\begin{array}{cc} \boldsymbol{\mathcal{B}}_{v}^{{\ast}}&\mathbf{0}_{ n_{1}\times k_{2}} \end{array} \!\right )^{{\ast}}$, which compared to (4.65) clearly preserve input-output structure. Therefore a netlist representation for the reduced impedance-type model can be obtained, that is driven injected currents just as the original circuit. This is done via the RLCSYN [176] unstamping procedure. To this end, we use the Laplace transform and convert (4.67) to the second order form:

$$\displaystyle\begin{array}{rcl} \left \{\begin{array}{rcl} [s\tilde{\boldsymbol{\mathcal{C}}} +\tilde{ \boldsymbol{\mathcal{G}}} + \frac{1} {s}\tilde{\varGamma }]\tilde{\mathbf{v}}(s)\!&\! =\!&\!\tilde{\boldsymbol{\mathcal{E}}}_{v}\mathbf{i}_{\mathit{in}}(s) \\ \tilde{\mathbf{y}}(s)\!&\! =\!&\!\tilde{\boldsymbol{\mathcal{E}}}_{v}^{{\ast}}\tilde{\mathbf{v}}(s),\end{array} \right.& &{}\end{array}$$

(4.70)

where $\tilde{\mathbf{i}}_{L}(s) = \frac{1} {s}\tilde{\boldsymbol{\mathcal{L}}}^{\!-1\!}\left (\tilde{\boldsymbol{\mathcal{E}}_{ l}}^{{\ast}}\right )\tilde{\mathbf{v}}(s)\ \ \mathrm{and}\ \ \tilde{\varGamma } =\tilde{ \boldsymbol{\mathcal{E}}}_{ l}\tilde{\boldsymbol{\mathcal{L}}}^{\!-1\!}\tilde{\boldsymbol{\mathcal{E}}}_{ l}^{{\ast}}.$

The presentation of RLCSYN follows [176, Sect. 4], [158] and is only summarized here. In circuit simulation, the process of forming the $\boldsymbol{\mathcal{C}},\boldsymbol{\mathcal{G}},\boldsymbol{\mathcal{L}}$ system matrices from the individual branch element values is called “stamping”. The reverse operation of “unstamping” involves decomposing entry-wise the values of the reduced system matrices in (4.70) into the corresponding R, L, and C values. When applied on reduced models, the unstamping procedure may produce negative circuit elements because the reduced system matrices are no longer diagonally dominant (while the original matrices were). Obtaining positive circuit elements only is subject to further research. The resulting Rs, Ls and Cs are connected in the reduced netlist according to the MNA topology. The reduced input/output matrices of (4.70) directly reveal the input connections in the reduced model via injected currents, without any controlling elements. The prerequisites for an unstamping realization procedure therefore are:

• 1. The original system is in MNA impedance form (4.66). If the system is of admittance type (4.64), apply the admittance-to-impedance conversion from Sect. 4.5.3.1.

• 2. In (4.66), no Ls are directly connected to the input terminals so that, after reduction, diagonalization and regularization preserve the input/output structure.

• 3. System (4.66) is reduced with SPRIM/IOPOR [176] to (4.67) and converted to second order form (4.70). The alternative is to obtain the second order form of the original system first, and reduce it directly with SAPOR/IOPOR [143, 176].

• 4. The reduced system (4.70) must be diagonalized and regularized according to [176]. Diagonalization ensures that all inductors in the synthesized model are connected to ground (i.e., there are no inductor loops). Regularization eliminates spurious over-large inductors. These steps however are not needed for purely RC circuits.

6.4 Numerical Examples

We apply the proposed reduction and synthesis framework on several test cases. The first is a simple circuit which illustrates the complete admittance-to-impedance formulation and the RLCSYN unstampting procedure, as described in Sect. 4.5.3. The second example is a SISO transmission line model, while the third is a MIMO model of a spiral inductor.

6.4.1 Illustrative Example

Fig. 4.25

Admittance-type circuit driven by input voltages [166]. G _1, 2, 3 = 0. 1S, $L_{1} = 10^{-3}H$, $C_{1,2} = 10^{-6}$, $C_{c} = 10^{-4}$, $\|u_{1,2}\| = 1$

The circuit in Fig. 4.25 is voltage driven, and the MNA admittance form (4.64) is:

$$\displaystyle\begin{array}{rcl} \left (\!\begin{array}{cccc|cc|c} 0 &0& 0 & 0 &0&0& 0\\ 0 &0 & 0 & 0 &0 &0 & 0 \\ 0 &0&C_{1} + C_{c}& - C_{c} &0&0& 0 \\ 0 &0& - C_{c} &C_{2} + C_{c}&0&0& 0 \\ \hline 0&0& 0 & 0 &0&0& 0\\ 0 &0 & 0 & 0 &0 &0 & 0 \\ \hline 0&0& 0 & 0 &0&0&L \end{array} \!\right )\!\dot{\left (\!\!\!\begin{array}{c} v_{1} \\ v_{4} \\ v_{2} \\ v_{3} \\ \hline i_{S_{1}} \\ i_{S_{2}} \\ \hline i_{L} \end{array} \!\!\!\right )}\! +\! \left (\!\!\!\begin{array}{cccc|cc|c} G_{1} & 0 & - G_{1} & 0 &1&0&0 \\ 0 & G_{3} & 0 & 0 &0&1&1 \\ - G_{1} & 0 &G_{1} + G_{2} & - G_{2} & 0&0&0 \\ 0 & 0 & - G_{2} & G_{2} & 0&0&1 \\ \hline - 1& 0 & 0 & 0 &0&0&0\\ 0 & - 1 & 0 & 0 &0 &0 &0 \\ \hline 0 & 1 & 0 & - 1 &0&0&0 \end{array} \right )\!\left (\!\!\!\begin{array}{c} v_{1} \\ v_{4} \\ v_{2} \\ v_{3} \\ \hline i_{S_{1}} \\ i_{S_{2}} \\ \hline i_{L} \end{array} \!\!\!\right )\quad & =& \left (\!\!\!\begin{array}{cc} 0 & 0\\ 0 & 0 \\ 0 & 0\\ 0 & 0 \\ \hline -\! 1& 0\\ 0 & -\!1 \\ \hline 0 & 0 \end{array} \!\!\!\right )\!\left (\!\!\!\begin{array}{c} u_{1} \\ u_{2}\end{array} \!\!\!\right ){}\end{array}$$

(4.71)

Notice that

$$\displaystyle\begin{array}{rcl} \mathbf{i}_{\mathit{in}}& =& \left (\begin{array}{c} \!i_{1} \\ i_{2} \end{array} \!\right ) = -\left (\begin{array}{c} \!i_{S_{1}} \\ i_{S_{2}} \end{array} \!\right ){}\end{array}$$

(4.72)

$$\displaystyle\begin{array}{rcl} \mathbf{u}\!& =& \!\left (\begin{array}{c} \!u_{1} \\ u_{2}\end{array} \!\right ) = \left (\begin{array}{c} \!v_{1} \\ v_{4}\end{array} \!\right ),{}\end{array}$$

(4.73)

thus the external nodes (input nodes/terminals) are v ₁ and v ₄, and the internal nodes are v ₂ and v ₃. As described in Sect. 4.5.3.1, (4.71) has an equivalent impedance formulation (4.66), with:

$$\displaystyle\begin{array}{rcl} \boldsymbol{\mathcal{C}} = \left (\!\begin{array}{cccc} 0&0& 0 & 0\\ 0 &0 & 0 & 0 \\ 0&0&C_{1}\! +\! C_{c}& -\! C_{c} \\ 0&0& -\! C_{c} &C_{2}\! +\! C_{c} \end{array} \right ),\ \boldsymbol{\mathcal{L}} = \left (\!\!\!\begin{array}{c} L \end{array} \!\!\!\right ),& \ \ \ \boldsymbol{\mathcal{G}} = \left (\!\!\!\begin{array}{cccc} G_{1} & 0 & -\! G_{1} & 0 \\ 0 &G_{3} & 0 & 0 \\ -\! G_{1} & 0 &G_{1}\! +\! G_{2} & -\! G_{2} \\ 0 & 0 & -\! G_{2} & G_{2} \end{array} \!\!\!\right ),\ \boldsymbol{\mathcal{E}}_{l} = \left (\!\begin{array}{cc} 0\\ -\!1 \\ 0\\ 1 \end{array} \!\right )&{}\end{array}$$

(4.74)

$$\displaystyle\begin{array}{rcl} \boldsymbol{\mathcal{E}}_{v} = \left (\!\!\!\begin{array}{cc} 1&0\\ 0 &1 \\ 0&0\\ 0 &0 \end{array} \!\!\!\right ),& \ \ \ \boldsymbol{\mathcal{B}} = \left (\!\!\!\begin{array}{cc} -\! 1& 0\\ 0 & -\!1 \end{array} \!\!\!\right ),\ \boldsymbol{\mathcal{B}}_{v} = -\!\boldsymbol{\mathcal{B}}&{}\end{array}$$

(4.75)

Matrices (4.74) and (4.75) are reduced either in first order form using SPRIM/IOPOR according to Sect. 4.5.3.2.

Here we reduce the circuit with SPRIM/IOPOR and synthesize it by unstamping via RLCSYN. Note that there is an L directly connected to the second input node v ₄, thus assumption 2. from RLCSYN is not satisfied. We thus reduce and synthesize the single-input-single-output version of (4.71) only, where the second input i ₂ is removed. Therefore the new incidence matrices are:

$$\displaystyle{ \boldsymbol{\mathcal{E}}_{v_{1}} = \left (\!\begin{array}{c} 1\\ 0 \\ 0\\ 0 \end{array} \!\right ),\boldsymbol{\mathcal{B}}_{1} = \left (\begin{array}{c} - 1 \end{array} \right ),\ \boldsymbol{\mathcal{B}}_{v_{1}} = -\!\boldsymbol{\mathcal{B}}_{1}. }$$

(4.76)

We choose an underlying PRIMA projection matrix $\mathbf{V} \in \mathbb{C}^{n\times k}$ spanning a k = 2-dimensional Krylov subspace (with expansion point s ₀ = 0). According to Sect. 4.5.3.2, after splitting V and appropriate re-orthonormalization, the dimensions of the input-output structure preserving partitioning are:

$$\displaystyle{ n_{1} = 1,\ n_{2} = 3,\ n_{l} = 1,\ k_{2} = 2,\ k_{3} = 1, }$$

(4.77)

and the SPRIM/IOPOR projection is:

$$\displaystyle\begin{array}{rcl} \tilde{\mathbf{W}} = \left (\!\begin{array}{llr|l} 1 &0 & 0&0 \\ 0 &4.082 \cdot 10^{-1} & - 4.861 \cdot 10^{-1} & 0 \\ 0 &8.164 \cdot 10^{-1} & 5.729 \cdot 10^{-1} & 0 \\ 0 &4.082 \cdot 10^{-1} & - 6.597 \cdot 10^{-1} & 0 \\ \hline 0&0 & 0&1 \end{array} \!\right ) \in \mathbb{C}^{5\times 4},\ \mathrm{with}\ \mathbf{W} \in \mathbb{C}^{4\times 3}.& &{}\end{array}$$

(4.78)

After diagonalization and regularization, the SPRIM/IOPOR reduced system matrices in (4.70) are:

$$\displaystyle\begin{array}{rcl} \tilde{\boldsymbol{\mathcal{C}}}& =& \left (\!\begin{array}{lrr} 0& 0& 0 \\ 0& 1.749 \cdot 10^{-5} & - 5.052 \cdot 10^{-5} \\ 0& - 5.052 \cdot 10^{-5} & 1.527 \cdot 10^{-4} \end{array} \!\right ),\ \ \tilde{\boldsymbol{\mathcal{G}}} = \left (\!\begin{array}{rrr} 1& 8.165 \cdot 10^{-2} & - 5.729 \cdot 10^{-2} \\ 8.165 \cdot 10^{-2} & 9.999 \cdot 10^{-2} & - 7.726 \cdot 10^{-2} \\ - 5.7295 \cdot 10^{-2} & - 7.7265 \cdot 10^{-2} & 2.084 \cdot 10^{-1} \end{array} \!\right ) \\ \tilde{\varGamma }& =& \left (\!\begin{array}{rrr} 0&0& 0\\ 0 &0 & 0 \\ 0&0&30.14 \end{array} \!\right ),\ \ \tilde{\boldsymbol{\mathcal{E}}}_{v_{1}} = \left (\!\begin{array}{r} 1\\ 0 \\ 0 \end{array} \!\right ){}\end{array}$$

(4.79)

Reduced matrices (4.79) are now unstamped individually using RLCSYN. The reduced system dimension in second order form is thus N = 3, indicating that the reduced netlist will have 3 nodes and an additional ground node. In the following, we denote by M _i, j i = 1… N, $j = 0\ldots N - 1$ a circuit element connected between nodes (i, j) in the resulting netlist. M represents a circuit element of the type: R,L,C or current source J.

By unstamping $\tilde{\boldsymbol{\mathcal{G}}}$, we obtain the following R values (for simplicity only 4 figures behind the period are shown here, nevertheless in implementation they are computed with machine precision $\epsilon = 10^{-16}$):

$$\displaystyle\begin{array}{rcl} R_{1,0} = \left [\mathop{\sum }_{ k=1}^{3}\tilde{\boldsymbol{\mathcal{G}}}_{ (1,k)}\right ]^{-1} = 8.0417\ \varOmega,\ \ R_{ 1,2} = -\left [\tilde{\boldsymbol{\mathcal{G}}}_{(1,2)}\right ]^{-1} = -12.247\ \varOmega,\ \ R_{ 1,3} = -\left [\tilde{\boldsymbol{\mathcal{G}}}_{(1,3)}\right ]^{-1} = 17.452\ \varOmega,& & {}\\ R_{2,0} = \left [\mathop{\sum }_{ k=1}^{3}\tilde{\boldsymbol{\mathcal{G}}}_{ (2,k)}\right ]^{-1} = 9.5798\ \varOmega,\ \ R_{ 2,3} = -\left [\tilde{\boldsymbol{\mathcal{G}}}_{(2,3)}\right ]^{-1} = 12.942\ \varOmega,\ \ R_{ 3,0} = \left [\mathop{\sum }_{ k=1}^{3}\tilde{\boldsymbol{\mathcal{G}}}_{ (3,k)}\right ]^{-1} = 13.535\ \varOmega.& & {}\\ \end{array}$$

By unstamping $\tilde{\boldsymbol{\mathcal{C}}}$, we obtain the following C values:

$$\displaystyle\begin{array}{rcl} C_{2,0} =\mathop{ \sum }_{ k=1}^{3}\tilde{\boldsymbol{\mathcal{C}}}_{ (2,k)} = -\!3.3026 \cdot 10^{-5}\ F,\ \ C_{ 2,3} = -\tilde{\boldsymbol{\mathcal{C}}}_{(2,3)} = 5.0526 \cdot 10^{-5}\ F,& & {}\\ \ \ C_{3,0} = \left [\mathop{\sum }_{ k=1}^{3}\tilde{\boldsymbol{\mathcal{C}}}_{ (3,k)}\right ]^{-1} = 1.0221 \cdot 10^{-4}\ F.& & {}\\ \end{array}$$

By unstamping $\tilde{\varGamma }$, we obtain the following L values:

$$\displaystyle\begin{array}{rcl} L_{3,0}& =& \left [\mathop{\sum }_{ k=1}^{3}\tilde{\varGamma }_{ (3,k)}\right ]^{-1} = 3.317 \cdot 10^{-2}\ H. {}\\ \end{array}$$

By unstamping $\tilde{\boldsymbol{\mathcal{E}}}_{v_{1}}$, we obtain the current source J _1, 0 of amplitude 1 A.

The Pstar [165] equivalent netlist is shown below:.

circuit;

     r r_1_0 (1, 0) 8.0417250765565598e+000;

     r r_1_2 (1, 2) -1.2247448713915894e+001;

     r r_1_3 (1, 3) 1.7452546181796258e+001;

     r r_2_0 (2, 0) 9.5798755840972589e+000;

     r r_2_3 (2, 3) 1.2942609947762115e+001;

     r r_3_0 (3, 0) 1.3535652691596653e+001;

     l l_3_0 (3, 0) 3.3170000000000033e-002;

     c c_2_0 (2, 0) -3.3026513336014821e-005;

     c c_2_3 (2, 3) 5.0526513336014765e-005;

     c c_3_0 (3, 0) 1.0221180442099465e-004;

     j j_1 (1, 0) sw(1, 0);

     c: Set node 1 as output: vn(1);

     c: Resistors 6;

     c: Capacitors 3;

     c: Inductors 1;

end;

Table 4.5 summarizes the reduction and synthesis results. Even though the number of internal variables (states) generated by the simulator is smaller for the SPRIM/IOPOR model than for the original, the number of circuit elements generated by RLCSYN is larger in the reduced model than in the original. Figure 4.26 shows that approximation with SPRIM/IOPOR is more accurate than with PRIMA. The Pstar simulation of the RLCSYN synthesized model also matches the MATLAB simulation of the reduced transfer function.

Table 4.5 Input impedance reduction (SPRIM/IOPOR) and synthesis (RLCSYN)

Fig. 4.26

Original, reduced and synthesized systems: PRIMA, SPRIM/IOPOR. The reduced and synthesized systems match but miss the peak around 4. 5 rad/s

Fig. 4.27

Transmission line from Sect. 4.5.4.2

6.4.2 SISO RLC Network

We reduce the SISO RLC transmission line in Fig. 4.27. Note that the circuit is driven by the voltage u, thus it is of admittance type (4.64). The admittance simulation of the model reduced with the dominant spectral zero method (Dominant SZM) [157, 161], synthesized with the Foster approach, is shown in Fig. 4.28. The behavior of the original model is well approximated for the entire frequency range, and can also reproduce oscillations at dominant frequency points.

Fig. 4.28

Input admittance transfer function: original, reduced with Dominant SZM in admittance form and synthesized with Foster admittance

Fig. 4.29

Input admittance transfer function: original and synthesized SPRIM/IOPOR model (via impedance), after reconnecting the voltage source at the input terminal

In Fig. 4.29 the benefit of the admittance-to-impedance transformation, described in Sect. 4.5.3.1, is seen. By reducing the system in impedance form with SPRIM/IOPOR and synthesizing (4.67) [using the second order form (4.70)] with RLCSYN [176], we are able to recover the reduced admittance (4.68) as well. The approximation is good for the entire frequency range.

6.4.3 MIMO RLC Network

We reduce the MIMO RLC netlist resulting from the parasitic extraction [153] of the coil structure in Fig. 4.30. The model has 4 pins (external nodes). Pin 4 is connected to other circuit nodes only via C’s, which causes the original model (4.66) to have a pole at 0. The example shows that the SPRIM/IOPOR model preserves the terminals and is synthesizable with RLCSYN without controlled sources.

Fig. 4.30

Coil structure from Sect. 4.5.4.3

Figure 4.31, shows the simulation of the transfer function from input 4 to output 4. SPRIM/IOPOR is more accurate around DC than PRIMA. Another alternative is to ground pin 4 prior to reduction. As seen from Fig. 4.32, SPRIM/IOPOR applied on the remaining 3-terminal system gives better approximation than PRIMA for the entire frequency range. With pin 4 grounded however, we loose the ability to (re)connect the synthesized model in simulation via all the terminals.

Fig. 4.31

Input impedance transfer function with “v ₄” kept: H ₄₄ for PRIMA, SPRIM/IOPOR and RLCSYN realization

Fig. 4.32

Input impedance transfer function with “v ₄” grounded: H ₃₃ for PRIMA, SPRIM/IOPOR and RLCSYN realization

6.5 Conclusions and Outlook

A framework for realizing reduced mathematical models into RLC netlists was developed. Model reduction by projection for RLC circuits was described and associated with two synthesis approaches: Foster realization (for SISO transfer functions) and RLCSYN [176] synthesis by unstamping (for MIMO systems). An admittance-to-impedance conversion was prosed as a pre-model reduction step and shown to enable synthesis without controlled sources. The approaches were tested on several examples. Future research will investigate reduction and synthesis methods for RCLK circuits with many terminals, while developments on sparsity-preserving model reduction for multi-terminal RC circuits can be found in [160].