⬇ Download Markdown  ·  ⬇ Download LaTeX  ·  ⬇ original  ·  view original  ·  CSV: table 1

INTERNATIONAL JOURNAL OF CIRCUIT THEORY AND APPLICATIONS
Int. J. Circ. ¹heor. Appl. 2000; 28:131}162
Structural analysis of electric circuits and consequences
for MNA
D. EsteHv ez Schwarz and C. Tischendorf*

1 Humboldt University of Berlin, Germany

2 Lunds University, Sweden

* Correspondence to: C. Tischendorf, Institute of Mathematics, Humboldt University of Berlin, D-10099 Berlin, Germany. The exact de"nition of the index of a DAE is given later in Section 3. Copyright 2000 John Wiley & Sons, Ltd. Received 2 November 1998 Revised 13 August 1999 SUMMARY The development of integrated circuits requires powerful numerical simulation programs. Naturally, there is no method that treats all the di!erent kinds of circuits successfully. The numerical simulation tools provide reliable results only if the circuit model meets the assumptions that guarantee a successful application of the integration software. Owing to the large dimension of many circuits (about 10 circuit elements) it is often di$cult to "nd the circuit con"gurations that lead to numerical di$culties. In this paper, we analyse electric circuits with respect to their structural properties in order to give circuit designers some help for "xing modelling problems if the numerical simulation fails. We consider one of the most frequently used modelling techniques, the modi"ed nodal analysis (MNA), and discuss the index of the di!erential algebraic equations (DAEs) obtained by this kind of modelling. Copyright 2000 John Wiley & Sons, Ltd. KEY WORDS: circuit simulation; di!erential-algebraic equation; DAE; index; modi"ed nodal analysis; MNA; structural properties; modelling; state-space form; state-variable approach; normal form; consistent initial values; topological criteria 1. INTRODUCTION The modern simulation of electric networks is based on modelling techniques that allow an automatic generation of the model equations. One of the most used technique is the modi"ed nodal analysis (MNA). It leads to di!erential}algebraic equations (DAEs) of the type f (x (t), x(t), t)"0. (1) Powerful numerical methods like the backward di!erence formulae (BDF) method can be applied directly to such DAEs. They are often used successfully in simulation packages. However they may fail. We know from investigations of general DAEs (cf. References [1}3]) that this is usually the case if the DAE has a higher index. Therefore, we are interested in easy checkable modelling

criteria that guarantee a low index. This question is closely related to two major problems in the state-variable analysis: 1. The uniqueness of solutions. 2. The determination of a minimal set of variables whose instantaneous values are su$cient to determine the state of the network completely. In other words, the formulation of the modelling equations in normal form, i.e. a reduction of Equation (1) to an explicit ODE. The corresponding variables are commonly denoted as state variables and they are relevant to "x consistent initial values, i.e. to "x initial values for which a solution of Equation (1) exists. Referring to this, "rst results were presented in Reference [4] for linear passive RLC networks. The state approach is here based on the construction of a normal tree, i.e. a tree that contains all independent voltage sources, no independent current sources, a maximal number of capacitive branches and a minimal number of inductive branches. Although the term &index' is not used in this paper, one can easily conclude that the index for such systems is 1 or 2, depending on the topology of the network. Afterwards, these results have been widely generalized for linear networks containing mutual inductances, gyrators, ideal transformers or controlled sources. In Reference [5], we "nd a detailed discussion of these generalizations and a current extension of the method based on the normal tree. Noteworthy here that all extensions are based on strategies using the construction of normal trees or (later on) matroids. Numerous authors have also studied non-linear networks with respect to the uniquely solvability and the determination of state variables (cf. e.g. References [6}17]). Typically, the results are based on the existence of speci"c trees or on certain positive de"nite and regular matrices, respectively. We will discuss these results in detail in Section 4. In Reference [14] topological criteria for unique solutions of nonlinear resistive circuits containing linear controlled sources have already been discussed. The authors apply a set of operations to the graph of the circuit and check a certain oriented structure, a cactus graph or a generalization thereof. Recently, some results in circuit theory, considering the mathematical Ansatz from the DAE point of view, have been established (cf. Reference [18}24]). By doing so, solvability criteria and results about the numerical solution of DAEs can be applied. Most of these results depend strongly on the index of a DAE. Roughly speaking, the index is a measure for the deviation of a DAE from an explicit ODE. DAEs of higher index (*2) are ill-posed in the sense that small perturbations in the initial data may cause arbitrarily large changes in the solution data. We focused our investigations onto the determination of the index for circuit systems. Under consideration of the large dimension (often 10) of the network systems, we are interested in topological criteria that can be checked very fast. Furthermore, the criteria should be based on local assumptions, i.e. we want to provide the opportunity to localize critical element modellings. In Reference [25], it has already been shown that, for non-linear time-independent networks without controlled sources, the index of the MNA equations does not exceed 2 and can be determined by topological criteria, assuming the positive de"niteness of the Jacobians of the element-characterizing functions. Afterwards, in Reference [26] it was proved that the standard circuit equations of linear as well as nonlinear RLCTG-networks, i.e. networks composed of independent sources, resistive, capacitive an inductive subnetworks, ideal transformers and gyrators, do not exceed 2, again under positive-de"niteness assumptions. In the present article, the results from Reference [25] are generalized for non-linear, time- dependent networks that may contain a wide class of controlled sources. Furthermore, many mathematically important structural properties of these di!erential}algebraic equations are 132 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Figure 1. n-Terminal circuit element. elaborated. For instance, the presented results can be employed to compute consistent initial conditions that has been performed in References [27, 28]. Further, the structural properties reveal stability properties of numerical integration methods if we apply the results from Reference [29]. We would like to point out that the required assumptions are not necessary to guarantee unique solvability, but they are su$cient to ensure a general description of structural properties. As already reported in Reference [14], it is far from hopeless to formulate a general existence and uniqueness theorem for non-linear circuits based only on topological conditions. In spite of that, graph-theoretic results are extremely useful since they are easy to check. The article is organized as follows. In Section 2, we introduce general structural properties of the networks and the equations arising from MNA. Section 3 describes brie#y the index concept, in particular the di!erential and the tractability index. In Section 4, the main results of this article are presented, whereas the proofs are outlined in Sections 5 and 6. 2. STRUCTURAL ANALYSIS We consider lumped electric circuits containing non-linear, time-variant resistances, capacitan- ces, inductances, voltage sources and current sources. Usually, circuit simulation tools are based on these kinds of network elements. For two-terminal (one-port) lumped elements, the current through the element and the voltage across it are well-de"ned quantities. For lumped elements with more than two terminals, the current entering any terminal and the voltage across any pair of terminals are well de"ned at all times (cf. Reference [30]). Hence, general n-terminal elements (see Figure 1) are completely described by (n!1) currents entering the (n!1) terminals and the (n!1) branch voltages across each of these (n!1) terminals and the reference terminal n. In particular, n-terminal resistances can be modelled by an equation system of the form j " r (u , 2 , u , t) for k"1,2 , n!1 if j represents the current entering the terminal k and u describes the voltage across the pair of terminals l, n (for k, l"1,2 , n!1). The Kirchho! 's current law implies the current entering the terminal n to be given by j " ! j . The conductance matrix G (u , 2 , u , t) is then de"ned by the Jacobian G (u , 2 , u , t) :" r u 2 r u r u 2 r u . STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 133 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

The index e shall specify the correlation to a special element of a circuit. Later on we will introduce the conductance matrix G(u, t) describing all resistances of a circuit. Correspondingly, the capacitance matrix C (u , 2 , u , t) of a general n-terminal capacitance is given by C (u , 2 , u , t) :" q u 2 q u q u 2 q u if the voltage}current relation is de"ned by means of charges by j " d dt q (u , 2 , u , t) for k"1,2 , n!1. In order to illustrate what the matrices C may look like, let us consider a MOSFET-model as an example of a common n-terminal element. Choosing the source node S as the reference node, we have the reference voltages u , u , and u . For the currents we obtain j " C u R # C (uR ! uR ), j " !C (uR ! uR ) !C (uR ! uR ) #d(u ! u ) #i(u , u , u ) # 1 R u j " C u R # C (uR ! uR )!d(u )!d(u ! u ). Note that j is given by the formula j " !j ! j ! j due to Kircho! 's Current Law. Now it is easy to verify that C (u , u , u )" C # C !C 0 !C C # C !C 0 !C C # C for the MOSFET-model from Reference [31] (see Figure 2). Inductances can be modelled by means of #uxes by u " d dt ( j , 2 , j , t) for k"1,2 , n!1. Then, the inductance matrix ¸ ( j ,2 , j , t ) of a general n-terminal inductance is given by the Jacobian ¸ ( j ,2 , j , t) :" j 2 j j 2 j . 134 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Originally developed at Berkeley in the 1970s and early 1980s, and subsequently commercialized by companies including MetaSoftware (HSPICE), MicroSim (PSPICE), Intusoft (IS} S PICE), Spectrum Software (Micro-Cap V), Cadence (Analog Workbench), Analogy (Saber), and Deutsch Research (DR. SPICE, ViewSpice). A Developed by SIEMENS. A commonly used method, for network analysis in circuit simulation packages like SPICE and TITAN,A is the modi"ed nodal analysis (MNA). It represents a systematic treatment of general circuits and is important when computers perform the analysis of networks automatically. The scheme to set up the MNA equations is: 1. Write node equations by applying Kirchho! 's current law (KCL) to each node except for the datum node: Aj"0. (2) The vector j represents the branch current vector. The matrix A is called the (reduced) incidence matrix and describes the network graph, the branch-node relations. 2. Replace the currents j of voltage-controlled elements by the voltage-current relations of these elements in Equation (2). 3. Add the current}voltage relations for all current-controlled elements. Note that, in case of multi-terminal elements with n terminals, we speak of branches if they represent a pair of terminals l, n with 1)l)n!1. In order to obtain more detailed information about the structure of the equations arising from MNA, we split the (reduced) incidence matrix A into the element-related incidence matrices A"(A , A , A , A , A ), where A , A , A , A , and A describe the branch-current relations for capacitive branches, inductive branches, resistive branches, branches of voltage sources and branches of current sources, respectively. Denote by e the node potentials (excepting the datum node) and by j and j the current vectors of inductances and voltage sources. De"ning the vector of functions for current and voltage sources by i and v, respectively, we obtain the following system from the MNA: A dq (Ae , t) dt #A r (A e , t)#A j # A j # A i A e, dq(Ae , t) dt , j , j , t " 0, (3) d( j , t) dt !Ae "0, (4) A e!v(Ae, dq(A e, t) dt , j , j , t)"0. (5) Note that the vectors A e, Ae , Ae , and Ae describe the branch voltages for the capacitive, inductive, resistive and voltage source branches, respectively. Remark. Owing to the fact that the currents through resistances are functions of the branch potentials, we do not include them separately as controlling functions. Of course, if the network STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 135 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

does not contain controlled sources, then the source functions reduce to functions i(t) and v(t) which depend on time only. Nowadays circuit simulation packages use two di!erent approaches for solving Equations (3}5), the conventional and the charge-oriented one. 136 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF

2.1. The conventional MNA

For the conventional MNA the vector of unknowns consists of all node voltages and all branch currents of current-controlled elements. De"ning C(u, t) :" q (u, t) u , q (u, t) :" q(u, t) t , ¸( j, t) :" ( j, t) j , ( j, t) :" ( j, t) t we obtainB A C (Ae , t) A de dt# A q (Ae , t)#A r (A e, t) #A j # A j # A i A e, A de dt , j , j , t " 0, (6) ¸( j , t) dj dt # ( j , t)!A e"0, (7) A e!v A e, A de dt , j , j , t " 0. (8) Later on we will also need G(u, t) :" r(u, t) u , r (u, t) :" r(u, t) t .

2.2. The charge-oriented MNA

In comparison with the conventional MNA, the vector of unknowns consists additionally of the charge of capacitances and the #ux of inductances. Moreover, the original voltage}charge and current}#ux equations are added to the system. The resulting system is then of the form (cf. Reference [23]) A dq dt #A r (A e, t)#A j # A j # A i (Ae, dq dt , j , j , t)"0, (9)

B Note that we have dq(A e, t) dt "C(A e, t) A de dt# q (Ae , t) Therefore, i(Ae, (dq(A e, t)/dt), j , j , t)"i * (Ae, A (de/dt), j , j , t) for a suitable function i * . An analogous relation is valid for the controlled voltage sources. For simplicity, we drop the index *. A dq dt #A r (A e, t)#A j # A j # A i (Ae, dq dt , j , j , t)"0, (9) Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

d dt !Ae "0, (10) A e!v (A e, dq dt , j , j , t)"0, (11) q!q (A e, t)"0, (12) ! ( j , t)"0. (13) STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 137

2.3. Topological characterization of the splitted incidence matrix

An explicit description of such projectors is given in Reference [27]. The splitting of the incidence matrix A"(A , A , A , A , A ) corresponding to certain branches leads to useful structural information for lumped circuits. In order to describe the di!erent parts of Equations (6)}(8) in more detail, we will introduce some useful projectors. Before doing this, let us recall the de"nition of a projector. De,nition 2.1. (1) A matrix Q3 is a projector onto R if and only if Q"Q and im Q"R . (2) A matrix Q3 is a projector along R if and only if Q"Q and ker Q"R . (3) For "R R a matrix Q3 is the uniquely de"ned projector onto R along R if and only if Q"Q, im Q"R , and ker Q"R . We denote by Q , Q< }C, Q , Q , QM , and QM< !C projectors onto ker A , ker A Q , ker A Q Q< }C, ker A , ker A , and ker Q A , respectively. The complementary projectors will be denoted by P :"I !Q, with the corresponding subindex. We observe that im P Lker P< }C , im P< }C Lker PR }C< and im P Lker PR }C< , and that thus Q Q < }C is a projector onto ker(A A ) and Q Q < }CQ R }C< is a projector onto ker(A A A ) . In order to shorten denotations, we use the abbreviation Q : " Q Q < }CQ R }C< . Remark that the projector P does not coincide with the projector PR }C< in general. The following theorem describes well-known topological properties in terms of the introduced incidence matrices and projectors. ¹heorem 2.2. Given a lumped circuit with capacitances, inductances, resistances, voltage sources and current sources. ¹hen, the following relations are satis,ed for the (reduced) incidence matrix A"(A A A A A ): 1. ¹hen matrix (A A A A ) has full row rank, because cutsets of current sources are forbidden. 2. ¹he matrix A has full column rank, because loops of voltage sources are forbidden. 3. ¹he matrix (A A A ) has full row rank if and only if the circuit does not contain a cutset consisting of inductances and/or current sources only. 4. ¹he matrix QA has full column rank if and only if the circuit does not contain a loop consisting of capacitances and voltage sources only. Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Note that loops containing only capacitances are excluded under point 4, whereas cutsets containing only inductances are included under point 3 of Theorem 2.2. In the following, the special cutsets and loops considered in Theorem 2.2 will be important. Therefore we de"ne: 1. An ¸}I cutset is a cutset consisting of inductances and/or current sources only. 2. A C}< loop is a loop consisting of capacitances and voltage sources only. Using the introduced projections we obtain the following corollary from Theorem 2.2. Corollary 2.3. ¹heorem 2.2 implies that 1. Q " 0 if and only if the network does not contain ¸}I cutsets, 2. QM< }C" 0 if and only if the network does not contain C}< loops. For a simpler description later on, we adduce two lemmata: ¸emma 2.4. If M is a positive-de,nite mm-matrix and N is a rectangular matrix of dimension km, then it holds that ker NMN"ker N and im NMN"im N The correctness of Lemma 2.4 follows immediately from the de"nition of positive-de"nite matrices. ¸emma 2.5. If C(A e, t), ¸( j , t) and G(A e, t) are positive de,nite, then the matrices H (Ae , t) :"A C (A e, t) A# Q Q H :"Q A A Q # Q <} C Q< }C H :" A Q Q A # QM <} C QM< }C H (Ae ) :"Q <} CQ A G (Ae , t) A Q Q < }C# Q R} C< QR }C< H ( j , t) :"Q A ¸ ( j , t) A Q # P P H (Ae , t) :"QM <} CA H (A e, t) A QM< }C# PM <} CP M< }C are regular. Proof. Using Lemma 2.4, the regularity of H (A e, t) is obvious since C(A e, t) is positive de"nite. For H and for H the regularity follows immediately, and for H analogously if we consider that G(A e, t) is positive de"nite. Let us prove the regularity of H . Let z be an element of ker H . Then we have (Q A ¸ ( j , t) AQ # P P ) z"0. If we multiply this equation by P , it results that P P z"0 and, therefore, P z "0. Hence, we obtain Q A ¸ ( j , t) A Q z"0. 138 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Then, since ¸ ( j , t) is positive de"nite, AQ z "0 holds. Applying that (A , A , A , A ) has full column rank, we conclude Q z"0, i.e. z"P z and, since P z"0, the regularity is veri"ed. The regularity from H (A e, t) can be easily shown making use of the facts that C(A e, t) is positive de"nite and that A has full column rank. 3. DAEs AND THEIR INDEX In Section 2, we observed that the MNA leads to a coupled system of implicit di!erential equations and non-linear equations, i.e. to a di!erential-algebraic equation (DAE) f (xR (t), x(t), t)"0 (14) where the partial derivative f (xR (t), x(t), t) is singular (cf. References [18, 21}23]). The analytical and numerical solutions of Equation (14) depend strongly on its structure and index. DAEs have, among other things, the following two important properties (see e.g. References [1}3]): (i) DAEs do not only represent integration problems, but also di!erentiation problems. Some parts of a DAE must be di!erentiable su$ciently often. (ii) Some components of the solution are determined algebraically. This implies that we cannot prescribe initial values for all variables.** Let us note that numerical methods can fail in higher index cases, particularly if the index is greater than 2. Typical problems to expect are extremely small step sizes and simulation interrupts caused be exceptions in numerical routines. Therefore, we are looking for conditions (depending on the network topology) that guarantee a lower index ()2). In the non-linear case, the index concept is not unique in the literature. In this article we analyse two important index concepts, the di!erential index and the tractability index, with regard to circuits. STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 139

3.1. Dexnition of the diwerential index

** The consequences of the results presented in this article referring this have been developed in References [27, 28]. The most general de"nition of the di!erential index of non-linear DAE systems is (cf. Reference [2]): De,nition 3.1. The di!erential index of the general non-linear, su$ciently smooth DAE f (x, x, t)"0 (15) Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

is the smallest such that f (x, x, t)"0, d dt f (x, x, t)"0, d dt f (x, x, t)"0 uniquely determines the variable x as a continuous function of (x, t). Note that the singularity of f (x, x, t) implies that Equation (14) contains some derivative-free equations which we will denote by explicit constraints. If the index is higher than 1, then combinations and substitutions of the original and the di!erentiated DAE may lead to further derivative-free equations, called hidden constraints. Fortunately, the structure of the DAEs that results from the MNA in circuit simulation is such that it will not be necessary to derive the whole function f. As we will see, it su$ces to derive the explicit constraints in index 1 case and, additionally, the hidden constraints in index 2 case. 140 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF

3.2. Dexnition of the tractability index

The tractability index [1, 32] orientates on the linearization of a DAE. This index concept requires only weak smoothness conditions. Furthermore, solvability and stability results exist for index-1-tractable and index-2-tractable DAEs (see, e.g. References [21, 20]). We consider non-linear DAEs f (x, x, t)"0 (16) for which N :"k er f (x, x, t) is constant and f is continuously di!erentiable. We denote A(x, x, t) :"f (x, x, t) and B(x, x, t) :"f (x, x, t). De,nition 3.2. DAE (16) is called index-1-tractable if the matrix A (x, x, t) :" A(x, x, t)#B(x, x, t) Q is regular for a constant projector Q onto N. Remarks. (1) The matrix A (x, x, t) is regular if and only if NS(x, x, t)"0 for S(x, x, t) :" z: B(x, x, t) z3im A(x, x, t). (2) The condition does not depend on the choice of the projector Q. For a proof see, e.g. Reference [1]. De,nition 3.3. DAE (16) is called index-2-tractable if 1. it is not index-1-tractable, 2. N (x, x, t) :"k er A (x, x, t) is of constant rank, 3. A ( x, x, t) :"A (x, x, t)#B (x, x, t) Q (x, x, t) is regular for a projector Q (x, x, t) onto N (x, x, t) and B (x, x, t) :"B (x, x, t) (I!Q). Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

For capacitances and inductances with a$ne characteristics the positive de"niteness implies that they are strictly locally passive (cf. Reference [17]). For reasons of simplicity, we do not consider the index-0 cases, which result if f (xR (t), x(t), t) is regular, separately. Remarks. (1) The matrix A (x, x, t) is regular if and only if N (x, x, t)S ( x, x, t)"0 for S (x, x, t):" z: B (x, x, t) z3im A (x, x, t). (2) The condition does not depend on the choice of the projector Q . For a proof see again Reference [1]. 4. THE INDEX OF DAEs RESULTING FROM THE MNA FOR ELECTRIC CIRCUITS The investigations of numerical methods for DAEs have shown that available codes for general nonlinear DAEs provide reliable results only for DAEs of lower index ()2). Therefore, we are interested in adequate conditions for electric circuits that guarantee a lower index DAE. In particular, the voltage-controlled voltage sources (VCVS), current-controlled voltage sources (CCVS), voltage-controlled current sources (VCCS), and current-controlled current sources (CCVS) have to be analysed very carefully. We consider the two de"ned index concepts for the systems arising form circuits. The di!erential index is investigated in Section 5 and the tractability index in Section 6. The results show that both concepts lead to the same index in case of circuit simulation applying MNA. They are summarized in the following theorems. ¹heorem 4.1. Consider lumped electric circuits containing resistances, capacitances, inductances, and voltage and current sources. ¸et the capacitance, inductance and conductance matrices of all capacitances, inductances, and resistances, respectively, be positive de,nite.- - Furthermore, let the following conditions for the controlled sources be satis,ed: 1. ¹he controlled voltage sources do not form a part of any C}< loop and their controlling elements ful,l the conditions exposed in the ¹ables I and II. 2. Each controlled current source ful,ls at least one of the following conditions: (a) It does not form a part of any ¸}I cutset and the controlling elements ful,l the conditions exposed in the ¹ables III and I<. (b) ¹here exists a path formed by capacitances that connects its incidence nodes. ¹he controlling elements ful,l the conditions exposed in ¹able < for CCCS, and the <CCS are controlled by an arbitrary voltage. (c) ¹here exists a path formed by capacitances and voltage sources that connects its incidence nodes. ¹he controlling elements ful,l the conditions exposed in ¹able <I for CCCS, and the <CCS are controlled by an arbitrary voltage. ¹hen, the conventional MNA leads to an index-1 DAE? ? if and only if the network contains neither ¸}I cutsets nor C}< loops. Otherwise, the conventional MNA leads to an index-2 DAE. ¹heorem 4.2. ¹he same conclusions as in ¹heorem 4.1 are valid under the same assumptions, if we consider the charge-oriented MNA instead of the conventional MNA. STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 141 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Table I. VCVS*condition (1) The controlling voltages of a VCVS can be voltages of: 1. Capacitances, 2. Independent voltage sources, 3. CCVSs that are controlled by: (a) Inductances, (b) Independent current sources, (c) Resistances or VCCSs for which the controlling nodes are connected by: i. Capacitances, ii. Independent voltage sources, iii. Paths containing only the elements described in (3(c)i), (3(c)ii), (d) Branches that form a cutset with the elements described in (3a), (3b) and (3c), 4. Branches that form a loop with the elements described in (1), (2) and (3). Table II. CCVS*condition (1) The controlling currents of a CCVS can be currents of: 1. Inductances, 2. Independent current sources, 3. Resistances or VCCSs for which the controlling nodes are connected by: (a) Capacitances, (b) Independent voltage sources, (c) VCVSs for which the nodes that incide with the controlling branch are connected by i. Capacitances, ii. Independent voltage sources, iii. Paths containing only the elements described in (3(c)i), (3(c)ii), (d) Paths containing only the elements described in (3a), (3b) and (3c), 4. Branches that form a cutset with the elements described in (1), (2) and (3). Table III. VCCS*condition (2a) The controlling voltages of a VCCS can be voltages of: 1. Capacitances, 2. Voltage sources, 3. Branches that form a loop with branches like those described in (1) and (2). Remarks: 1. The presented criteria can be checked locally. It is neither necessary to "nd special trees nor to make additional assumptions on the functions and parameters that de"ne the controlled sources. Usually, it is not di$cult to check whether a model of a network element including controlled sources satis"es these conditions or not. 2. If a model of a network element does not satisfy the conditions, it is not di$cult to ful"ll them by introducing some additional capacitances, resistances or inductances into the model for this element. 3. Nevertheless, the topological assumptions made for the controlled sources are su$cient but not necessary. 142 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Table IV. CCCS*condition (2a) The controlling currents of a CCCS can be currents of: 1. Inductances, 2. Independent current sources, 3. Resistances or VCCSs for which the controlling nodes are connected by: (a) Capacitances, (b) Voltage sources, (c) Paths containing only the elements described in (3a) and (3b), 4. Branches that form a cutset with the elements described in (1), (2) or (3). Table V. CCCS*condition (2b) The controlling current of a CCCS can be the current of: 1. Inductances, 2. Independent current sources, 3. Resistances, 4. Voltage sources that do not form a part of a C}V loop, 5. VCCS, 6. A branch that forms a cutset with the elements described in (1), (2), (3), (4) and (5). Table VI. CCCS*condition (2c) The controlling current of a CCCS can be the current of: 1. Inductances, 2. Resistances, 3. Independent current sources, 4. VCCS, 5, A branch that forms a cutset with the elements described in (1), (2), (3) and (4). 4. Comparing the class of networks satisfying the assumptions of Theorem 4.1 with the class of allowable networks described in Table 10-3-1 in Reference [10], the assumptions for the controlled sources di!er mainly in two aspects: 4.1. In Reference [10], branch currents of C}< loops and branch voltages of ¸}I cutsets are not allowed to be controlling variables for controlled sources. However we allow that branch voltages of ¸}I cutsets appear as controlling variables under certain circum- stances. 4.2. We forbid controlled voltage sources in C}< loops and controlled current sources in ¸-I cutsets whereas they are allowed in Reference [10] if they depend only on a voltage of a tree capacitor or the current of a cotree inductor for a normal tree. In other words, controlled voltage sources in C}< loops and controlled current sources in ¸}I cutsets are allowed if they depend only on state variables. Following the proof for the existence of normal-form equations in Reference [10] it is easy to verify that a di!erentiation is necessary for all tree inductor voltages and all cotree STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 143 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

capacitor currents. In other words, the index of the DAE is 2 if and only if the network contains a C}< loop or an ¸}I cutset. Observe that, in this case, C-only loops have to be added to the class of C}< loops since the currents through C-only loops belong to the network variables whereas these currents are excluded in MNA formulations. If the network does not contain C}< loops or ¸}I cutsets then the index is 1, i.e. the results correspond to our results. The approach in Reference [10] assumes additionally that the global system matrices Z (de"ned in Equation (10}35a)) and M (de"ned in Equations (10}46)) have to be non- singular. The authors say that one can always satisfy these assumptions if one perturbes some element parameters. They do not give an advice which parameters should be pertur- bed. But the enormous dimension of nowadays relevant systems requires a localization of those parameters which should be perturbed. That is why we assumed the element related matrices to be positive de"nite which is a condition that can be controlled locally. 5. Corresponding results for linear systems are already presented in Reference [8]. They base on a normal tree for which the controlled sources (in this paper only two-ports are considered) have to satisfy the following conditions: 5.1. Elements with only impedance matrix representation (e.g. CCVS) must be cotree elements. 5.2. Elements with only admittance matrix representation (e.g. VCCS) must be tree ele- ments. 5.3. Elements with only hybrid matrix representation (e.g. CCCS, VCVS) must have the admittance branch in the tree and the other branch in the cotree. 6. The assumption that the element characteristic matrices C and ¸ are positive de"nite can be found in numerous articles (cf., among others, [8, 11, 13]). Moreover, in References [9, 25, 26], we "nd already the assumption that the matrices C, ¸, and G have to be positive de"nite. But all consider only nonlinear time-invariant networks without controlled sources. 7. More recently, several geometrical approaches (cf. References [11}13]) have been estab- lished. These results re#ect exactly the geometrical index approach (cf. References [33, 34]). All papers deal with time-invariant networks and base on the transversality condition: the space of branch voltages and branch currents satisfying the constitutive relations and the Kirchho! space are transversal. In Reference [12], only systems that do not contain C-loops and ¸-cutsets (i.e. index-1 systems because of the time-invariance) are considered. The index-2 case is developed in Reference [13] (without using the term &index'). 8. Similar results to those in Theorem 4.1 are reported for nonlinear networks containing multiports in Reference [35]. But, unfortunately, the assumptions on controlled sources are not speci"ed at all. Example: (1) Consider again the MOSFET-model given in Figure 2. The VCCS from source to drain is controlled by the branch voltages u , u , and u . For this, the conditions (2a)}(2c) are satis"ed since there are capacitive ways from gate to source, from drain to source as well as from bulk to source, and there exists a capacitive way from source to drain. (2) Consider the VCCS in Figure 3 (from Reference [10]). The considered CCVS does not form a part of a C}< loop and it is controlled by the current of a branch that forms a cutset with inductances. Therefore, it meets the condition (1) of Theorem 4.1. 144 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Figure 2. MOSFET-model. Figure 3. Circuit with CCVS. Corollary 4.3. ¹he assumption of ¹heorem 4.1 on the resistances can be slightly reduced. In fact, only the positive de,niteness of the conductance matrix corresponding to those resistances that do not form a loop with capacitances and/or voltage sources is required. This statement follows immediately from Theorem 4.1 if we consider the resistances as VCCS. In order to obtain a description of assumption (1) by means of projectors, we split the incidence matrix A into (A A ) for independent and controlled sources, respectively. ¸emma 4.4. ¹he condition that controlled voltage sources do not form a part of a C}< loop is equivalent to QM< }C" ( QM< }C) 0 . Here, (QM< }C) denotes the upper part of QM< }C corresponding to A . STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 145 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Proof. A controlled voltage source forms a part of a C}< loop if and only if the column a of A corresponding to this source depends linearly on the columns of (A A M ) , where AM denotes the matrix A reduced by the column a , i.e. there is a vector v such that (A A ) v"0 and v O0 for the sth component of v corresponding to the controlled source considered. That means, there is a vector v such that QA v "0 and v O 0, i.e. the sth row of QM< }C has a non-zero entry. This is equivalent to QM< }C O ( QM< }C) 0 . Hence, assumption (1) of Theorem 4.1 implies that QM< } C v A e, dq(A e, t) dt , j , j , t " QM <} C v (t), (17) v A e, dq(A e, t) dt , j , j , t " v * (A e, j , t), (18) for a suitable function v * and for a vector v (t) that contains the functions of independent voltage sources and zeros instead of the functions of controlled voltage sources. In the following we will drop the index *. In order to transcribe the assumptions made for controlled current sources, we split the incidence matrix A into (A , A , A , A ) and the current vector i correspondingly, for the independent current sources and the controlled current sources that ful"ll Equations (2a)}(2c), respectively. If a controlled current source ful"lls more than one of conditions (2a)}(2c), the corresponding column of A should be assigned to only one of the matrices A , A , and A . ¸emma 4.5. ¹he condition that controlled current sources do not form a part of an ¸}I cutset is equivalent to the relation Q A " (Q A 0). Proof. A controlled current source forms a part of an ¸}I cutset if and only if the column a of (A , A , A ) corresponding to this controlled source is linearly independent of the columns belonging to (A , A , A ) , i.e. a im (A A A ) and, therefore, Q a O 0. But, this is equivalent to the condition that Q (A , A , A ) O0. Thus, assumption (2a) of Theorem 4.1 implies that Q A i A e, dq(A e, t) dt , j , j , t " Q A i , (19) i A e, dq(Ae , t) dt , j , j , t " i (A e, A e, j , t), (20) for a suitable function i . 146 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Furthermore, assumption (2b) of Theorem 4.1 implies by de"nition that Q A " 0, (21) i Ae, dq(A e, t) dt , j , j , t " i (A e, j , PM< }C j , t ) (22) for a suitable function i . Finally, assumption (2c) of Theorem 4.1 implies that Q<} CQ A " 0 (23) i A e, dq(A e, t) dt , j , j , t " i (A e, j , t) (24) for a suitable function i . Regarding Equations (19), (21), and (23), the assumptions imply that Q A i A e, dq(A e, t) dt , j , j , t " Q A i (25) is always ful"lled. To shorten denotations we write i(A e, j , P< }C j , t) (26) when we do not distinguish between Equations (20), (22), and (24). The proofs of the theorems follow in the next sections. 5. THE DIFFERENTIAL INDEX OF THE DAE SYSTEMS IN CIRCUIT SIMULATION In this section we obtain the di!erential index of the DAE system as well as expressions for the constraints. In the following, we assume that the required smoothness is given. ¹heorem 5.1. Consider lumped electric circuits satisfying the assumptions of ¹heorem 4.1. ¹hen it holds: 1. If the network contains neither ¸}I cutsets nor C}< loops, then the conventional MNA leads to a DAE system with di+erential index-1 and the constraints are only the explicit ones: Q [A r (A e, t)#A j # A j # A i (Ae, j , t)]"0, (27) A e!v (A e, j , t)"0. (28) 2. If the network contains ¸}I cutsets or C}< loops, then the conventional MNA leads to a DAE system with di+erential index-2. =ith regard to the constraints, we distinguish the following three possibilities. (a) If the network does not contain an ¸}I cutset (but contains C}< loops), then the constraints are the explicit ones, namely Equations (27) and (28), and, additionally, the hidden constraint: QM <}C A H (A e, t) P [A q (A e, t)#A r (A e, t)#A j #A j # A i (Ae, j , PM< }C j , t)]#QM< } C dv dt " 0. (29) STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 147 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

AA The expressions for the explicit and the hidden constraints are of special interest with regard to a consistent initialization (cf. References [27, 28]). (b) If the network does not contain C}< loops, but contains ¸}I cutsets, the constraints are the explicit ones, (27) and (28), and, additionally, the hidden constraint: Q A ¸ ( j , t) (A e! ( j , t) # A di dt " 0. (30) (c) If the network contains ¸}I cutsets and C}< loops, then the MNA leads to a DAE system with di+erential index-2. In this case, the constraints are the explicit ones, (27) and (28), and the hidden ones (29) and (30).A A Remember that the functions v (t) and i (t) represent the functions of the independent voltage and current sources and that the matrices H ())}H ()) were de"ned in Lemma 2.5. Proof. In the following, we will take advantage of the fact that the analysed system is quasi-linear and that the matrices C(A e, t), ¸( j , t) and G(A e, t) are positive de"nite. Our aim is to obtain a representation of de/dt, dj / dt, dj / dt as continuous functions of e, j and j . To this purpose, we consider the following splittings: de dt "P de dt# Q P< }C de dt# Q Q < }C PR }C< de dt# Q de dt , dj dt " PM <}C dj dt # QM <}C dj dt . First, we make a general approach and afterwards we distinguish the di!erent cases with regard to the topological properties of the network. Step 0: If we multiply Equation (6) by H (A , t) P and Q , respectively, we obtain P de dt" !H (A e, t) P [A q (A e, t)#A r(A e, t)#A j #A j # A i (A e, j , P< }C j , t)] (31) and Equation (27). As ¸( j , t ) is regular, we obtain equations for dj / dt directly from Equation (7) dj dt " ¸ ( j , t) (A e! ( j , t )). (32) Note that the arguments of the controlled sources in Equations (31), (27), and (28) are written in accordance with Equations (18)}(26). Step 1: Next, we di!erentiate Equations (28) and (27), i.e. the constraints, and split them in the following way: Step 1a: Using Equation (17) we split the derivative of Equation (28) into QM <} C A P de dt" QM <} C dv dt (33) 148 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF

Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

and PM <} C A P # Q de dt" PM <} C dv (A e, j , t) dt . (34) If we consider Equation (33), we can realize that P (de/dt) can be substituted making use of Equation (31) to achieve the hidden constraint (29). Step 1b: Using Equation (25) we split the derivative of Equation (27) into Q A dj dt #A di dt " 0, (35) PR} C< Q<} C Q A G (A e, t) A de dt# A r (A e, t)#A dj dt # A di (A e, A e, j , t) dt " 0 (36) and P<} C Q A G (A e, t) A de dt# A r (A e, t)#A dj dt # A dj dt # A di (A e, j , t ) dt " 0. (37) Taking into account Equation (32), Equation (35) leads to the hidden constraint (30). Step 2: Finally, we di!erentiate the two hidden constraints (30) and (29) obtained in the last step: d dt (Q A ¸ ( j , t) (A e! ( j , t)))#Q A di dt " 0 (38) and d dt (QM <} CA H (A e, t) P [A q (A e, t)#A r (A e, t) #A j # A j # A i (Ae, j , PM< }C j , t)])#QM <} C dv dt " 0. (39) Step 3: Let us now take into account the di!erent topological properties of the systems we mentioned in Theorem 4.1: 1. If the network does not contain ¸}I cutsets, then Q " 0 (cf. point 1 in Corollary 2.3). Thus, in this case there is no hidden constraint (30). Moreover, as we have de/dt" P (de/dt)#Q P < }C (de/dt)#Q Q < }C PR }C< (de/dt) then, already Step 1 leads to an expres- sion for de/dt. If we multiply Equation (34) by H QA after substituting expressions (31) for P (de/dt) and (32) for dj / dt, we obtain an expression for P< }C (de/dt). Then, substituting P (de/dt)#Q P< }C (de/dt) and dj / dt into Equation (36) and multiplying by H ( ) ), we obtain a representation for PR }C< (de/dt). Note that these transformations are reversible by multiplication by HA Q H and H ( ) ), respectively. 2. If the network contains an ¸}I cutset, then Q O 0 (cf. point 1 in Corollary 4). Therefore, we consider de dt" P de dt# Q P < }C de dt #Q Q < }C PR }C< de dt# Q de dt STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 149 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

BB This variation of the order changes the spaces associated with the DAE-system, as will be shown in Lemma 6.2. and observe that we obtain the needed expression for Q (de/dt) when multiplying Equation (38) by H ( ) ) after substituting the expressions for P (de/dt)#Q P < }C (de/dt)# Q Q< }C PR }C< (de/dt) and dj / dt. 3. If the network does not contain C}< loops, then Q A has full column rank (cf. point 4 in Theorem 2.2). Therefore, PM< }C" I, and we obtain an expression for dj / dt when multiplying Equation (37) by HA Q after substituting the obtained expressions for de/dt and dj / dt. This transformation is reversible as well, as can be seen by multiplication by HQ A H . On the other hand, as QM< }C" 0, there is no hidden constraint (29). 4. If the network contains a C}< loop, then QA does not have full column rank (cf. point 4 in Theorem 2.2). Therefore, QM< }CO 0, and we obtain an expression for QM< }C (d j / dt) from Equation (39) by multiplication by H ( ) ) after the substitution of de/dt, dj / dt and PM< }C (dj / dt). Note that this is successively possible because of Equations (19)}(24) and that it is important to achieve "rst the complete expression for de/dt and afterwards those for dj / dt, because of the allowed controlling elements in Equation (2c).B B Step 4: Now we analyse the possible cases: 1. If the network contains neither ¸}I cutsets nor controlled C}< loops, both equations, (29) and (30), do not appear, i.e. we obtain a representation for de/dt, dj / dt, dj / dt as functions of e, j and j with the expressions obtained in Step 1. Thus, the di!erential index of the system is 1 and no hidden constraints appear. 2. In the other three cases, one more di!erentiation has to be carried out in order to "nd explicit expressions for the derivatives. Therefore, the di!erential index is 2. With Step 3 the statements of the theorem follow immediately from Step 2. ¹heorem 5.2. If the di+erential index is 1, then the network contains neither C}< loops nor ¸}I cutsets. If the di+erential index is 2, then the network contains at least a C}< loop or an ¸}I cutset. Proof. Let us now suppose that the di!erential index is 1. Then the hidden constraints have to be trivial, i.e. if we regard the homogeneous system, we obtain QM <}C A P de dt" 0, (40) Q A dj dt " 0. (41) Making use of the fact that A and (A , A , A , A ) have full row rank, we obtain QM< }C" 0 and Q " 0 (cf. Theorem 2.2), i.e. the network does not contain C}< loops or ¸}I cutsets. If the index is supposed to be 2, then at least one constraint has to appear, i.e. either QM< }C or Q has to be nontrivial (or both). Corollary 2.3 implies that the network has to contain at least a C}< loop or an ¸}I cutset. 150 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Proof of ¹heorem 4.2. To conclude, we observe that Theorem 5.1 holds analogously for the charge-oriented MNA. The results obtained with the di!erential index method are basically the same as those for the conventional MNA. To shorten denotations, we drop the arguments of the controlled sources, because they appear in the same way as in the proof of Theorem 5.1. Analogously to Step 0 from the proof of Theorem 4.1, we can split Equation (9) into A dq dt #P (A r (A e, t)#A j # A j # A i)"0, (42) Q (A r (A e, t)#A j # A j # A i )"0. (43) If we de"ne QM as a projector onto ker A , we can de"ne the matrix HM :"A A # QM Q M , which is regular, and obtain the expression PM dq dt "!HM A P (A r(A e, t)#A j # A j # A i) by multiplication of Equation (42) by HM A . Note that this transformation is reversible by multiplication by HM A A A , if HM :"A A # QQ . As Equation (10) is already an expres- sion for d/dt, the constraints are Equations (11}13) and (43). The derivatives of Equations (12) and (13) can be splitted as follows: PM dq dt !PM C (A e, t) A de dt! PM q (A e, t)"0, (44) QM dq dt !QM C(A e, t) A de dt! QM q (A e, t)"0, (45) d dt !¸ ( j , t) dj dt ! ( j , t)"0. (46) From Equation (44) we obtain the following expression for P (de/dt) and multiplication by H (A e, t) A P de dt" !H (A e, t) P (A r(A e, t)#A j # A j # A i) !H (A e, t) A q (A e, t). Note that this holds because of P H ( ) ) A HM A P" H( ) ) A HM AAA H M P" H ( ) ) P . PM Inserting this into Equation (45), we obtain an equation for QM ( dq/dt). On the other hand, Equation (46) leads to the expression (32) for dj / dt. As the constraints (11) and (43) are the same as Equations (27) and (28) in the conventional MNA, the expressions for the remaining deriva- tives are identical. This implies that the index statements of Theorem 5.1 are valid for the charge-oriented MNA, too. STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 151 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Remark: Observe that only the required smoothness has to be given in each case, and that we can recognize the smoothness requirements directly in the above equations. The next chapter shows how it is possible to de"ne an index with considerably fewer smoothness assumptions on the variables and on the input functions. This is specially relevant for circuit simulation because, in general, only low smoothness is given. 6. THE TRACTABILITY INDEX OF THE DAE SYSTEM IN CIRCUIT SIMULATION Note that the assumption N:" k er f (x, x, t) is constant is given for the quasi-linear DAEs (6)}(8) (cf. Equations (50)) and (9)}(13). For shorter expressions we drop the arguments in the following section. In order to distinguish between constant and non-constant terms, we will use a dot as an argument for non-constant terms. ¹heorem 6.1. ¸et the assumptions of ¹heorem 4.1 be satis,ed. ¹hen it holds: 1. If the network contains neither ¸}I cutsets nor C-< loops, then the conventional MNA leads to an index-1 tractable DAE system. 2. If the network contains ¸}I cutsets or C}< loops, then the conventional MNA leads to an index-2 tractable DAE system. ¹he canonical projector Q ( ) ) onto N (x, t) along S is given by H ( ) ) A Q M< }C H ( ) ) QM< }C AP Q H ( ) ) Q A !P Q X ( ) ) Q H ( ) ) Q A 0 0 ¸ ( ) ) AQ H ( ) ) Q A 0 !QM <}C H ( ) ) QM< }C A P !A >( ) ) Q H ( ) ) Q A 0 (47) where the matrices X( ) ) and >( ) ) are chosen in such a way that A di ( ) ) de Q " A C( ) ) A Q X( ) )#A A > ( ) ). Note, the matrices H ( ) ), H ( ) ), and H ( ) ) were de"ned in Lemma 2.5. Remark. The existence of such matrices X( ) ) and >( ) ) is satis"ed since the relation Q<} C Q A (di ( ) )/de)"0 is true (cf. Equations (21) and (23)). Before we will prove this theorem, we want to consider the special structure of A( ) ), B( ) ), Q( ) ), S( ) ), A ( ) ), B ( ) ), Q ( ) ), and S ( ) ) in case of circuit simulation. Writing system (6)}(8) as a non-linear DAE (16) with A(x, x, t) :"f (x, x, t) and B (x, x, t) :"f (x, x, t), we obtain that A( ) )" A C ( ) ) A 0 0 0 ¸( ) ) 0 0 0 0 (48) 152 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

and B ())" A C M ( ) ) A# A G( ) ) A # A di( ) ) de A # A di( ) ) dj A # A di( ) ) dj !A ¸M ( ) ) 0 A! dv( ) ) de ! dv( ) ) dj 0 (49) with CM (u, u, t)" d du C (u, t) u# d du q (u, t) and ¸M ( j , j , t )" d dj ¸( j , t) jR # d dj ( j , t ). Let us remark here that A ( ) ) represents the leading coe$cient matrix. It has a di!erent meaning than the incidence matrix A"(A , A , A , A , A ) . We will not use the notation A any longer. Therefore, this denotation should be acceptable. Since C ( ) ) is positive de"nite, we may conclude that ker A( ) )"ker A 0n (50) and im A( ) )"im A n 0. (51) Here, n describes the number of voltage sources and n describes the number of inductances in the network. Note, the null-space of A( ) ) as well as the image-space of A( ) ) are constant in any case. The null-space of A( ) ) describes the non-dynamic components of the circuit. For further considerations let us introduce a projector Q onto ker A( ) ) as Q" Q 0 0 0 0 0 0 0 I . For the de"nition of Q see Section 2.3. The space S( ) )"z: B( ) ) z3im A( ) ) describes all solution components for which we do not "nd an algebraic representation. Regarding Equation (51) it is given by S( ) )" z : A ! dv( ) ) de z ! dv( ) ) dj z " 0, A G( ) ) A# A di( ) ) de z # A # A di( ) ) dj z # A # A di( ) ) dj z 3im A . Consider the space NS( ) ). It represents all components that are determined neither by a di!erential equation nor by an algebraic equation. If NS( ) )O0, then these components can STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 153 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

be determined only by inherent di!erentiation instead of integration. The next lemma provides a possibility to determine from the network topology whether a di!erentiation problem is involved in the DAE (3.3) obtained applying MNA. This has a big in#uence onto numerical solving since di!erentiation problems are ill-posed in the sense of Hadamard, i.e. small perturba- tions in the input data can provide arbitrarily large perturbations in the output data. ¸emma 6.2. ¸et the conditions of ¹heorem 4.1 be satis,ed. ¹hen it holds that NS( ) )"im Q 0 0 0 0 0 !PM <}C Z( ) ) Q 0 QM< }C is true for a matrix Z( ) ) satisfying Q A (di ( ) )/de)"Q A Z ( ) ). Remarks. (1) The existence of such a matrix Z ( ) ) is guaranteed by condition (2c) of Theorem 4.1 (cf. Equation (23)). (2) Regarding the de"nitions of Q and QM< }C on Section 2.3 as well as Theorem 2.2, Lemma 6.2 implies that the network equations involve a di!erentiation problem if and only if the network contains a C}< loop or an ¸}I cutset. (3) If all controlled current sources satisfy conditions (2a) or (2b) of Theorem 4.1, then the relation NS ( ) )"im Q 0im QM< }C is true. (4) The di!erent structure of the general case and the one discussed in the latter point corresponds to the alteration of the order in which we solve the system for the di!erential index (cf. footnote B ). At this point it is recognizable that NS( ) ) represents those components for which the di!erential index de"nition requires two di!erentiations to obtain the representation of their derivative as a continuous function of the variables. Proof. Firstly, we show that the relation &-' is true. Assuming z3NS()) we know that z " Q z , z " 0 and z3S( ) ). Using Equations (18), (20), (21), and (24) we obtain A z " 0, (52) Q A G( ) ) A Q z # Q A di ( ) ) de z # Q A z " 0. (53) Then, Equation (52) provides additionally that Q<} CQ A (di ())/de) z " 0 (cf. Equation (23)). Multiplying Equation (53) by Q<} C and regarding AQ z " 0 we obtain Q<} C Q A G( ) ) A Q Q< }C z " 0. 154 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Since G( ) ) is positive de"nite, this implies A Q Q < }C z " 0, i.e. A z " 0 and so z 3im Q . Now relation (53) implies that Q A z " !QA di ( ) ) de "!Q A Z ()) z " !Q A Z ( ) ) Q z , i.e. z " !PM <}C Z( ) ) Q z # QM <}C z . Secondly, we show that the relation &.' is satis"ed. Assume that z " Q z and z " 0. Furthermore, we have z " QM <}C z ! PM <}C Z( ) ) z . (54) Then z3N"ker A( ) ) holds trivially and A ! dv( ) ) de z ! dv( ) ) dj z " dv( ) ) de Q z " 0 (55) is ful"lled. Using Equation (54) we obtain additionally that Q ( A G( ) ) A# A di( ) ) de z # A # A di( ) ) dj z # A # A di( ) ) dj z "Q A di ( ) ) de z # A z " Q A Z( ) ) z # Q A z " 0. Corollary 6.3. ¸et the conditions of ¹heorem 4.1 be satis,ed. ¹he network equation system obtained applying MNA is index-1-tractable if and only if the network contains neither a C}< loop nor an ¸}I cutset. Let us now study the higher index case. For that we investigate A ( ) ) and B ( ) ) de"ned in Section 3.2. A ( ) )" A C ( ) ) A# A G( ) ) A Q # A di( ) ) de Q 0 A # A di( ) ) dj !A Q ¸( ) ) 0 A Q 0 0 B ( ) )" A C M ( ) ) A# A G( ) ) AP # A di( ) ) de P A # A di( ) ) dj 0 !AP ¸M ( ) ) 0 AP ! dv( ) ) de P 0 0 STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 155 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

¸emma 6.4. ¸et the conditions of ¹heorem 4.1 be satis,ed. ¹hen the relation im A ( ) )"ker Q 0 0 0 0 0 0 0 QM <} C is satis,ed. Proof. Firstly, im A ( ) )-ker Q n ker QM <}C holds trivially, because of Q A di( ) ) de "0 and Q A di( ) ) dj "0 for all admitted controlled current sources (see Equations (19), (21), and (23)). Secondly, we assume that z3ker Q n ker QM< } C , i.e. Q z " 0 and QM< }Cz " 0. Then, there is an such that z " A Q . (56) Since Q A " 0 (see Equations (19), (21), and (23)), the relation z ! A G( ) ) A Q P < }C ! A di( ) ) de Q P < }C 3ker Q holds, i.e. there are , and such that z ! A G( ) ) A Q P < }C ! A di( ) ) de Q P< }C "A C( ) ) A # A G ( ) ) AQ Q < }C # A . (57) This is a simple conclusion of the fact that ker Q " im (A C( ) ) A, A G( ) ) A Q Q < }C , A A) since C( ) ) and G( ) ) are positive de"nite. Regarding Equations (20), (22), and (24) we obtain that A di( ) ) dj "A di ( ) ) dj PM< }C . (58) Considering Equation (23) we see that di ( ) ) de Q " di (A e, A e, j , t) de Q " di ( ) ) de Q P< }C . (59) Regarding Equation (23) we "nd and such that A di ( ) ) de Q Q< }C " A C( ) ) A # A . (60) Using Equation (21) we "nd and such that A di ( ) ) de Q Q< }C " A C( ) ) A , (61) 156 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

A di ( ) ) dj ( ! ) "A C( ) ) A . (62) Choosing :"P ( ! ! ! ) #Q P < }C # Q Q < }C , :"¸ ( ) ) (z # A Q ), :" ! and regarding Equations (56)}(61), we obtain that z"A ( ) ) 3im A ( ) ). Considering B ( ) ) and Lemma 6.4 we obtain a simple description of the constant space S : S " ker QM <} C A P ker Q A Rn . (63) For a de"nition of S see Section 3.2. ¸emma 6.5. ¸et the conditions of ¹heorem 4.1 be satis,ed. ¹hen, the canonical projector onto N ( ) )"kerA ( ) ) along S is given by Equation (47). Proof. 1. Q ( ) ) is a projector, since QM< }C H ( ) )"H ( ) ) QM <}C . H ( ) ) QM< } C A H ( ) ) A QM< }C" QM <}C , P Q " 0, Q H ( ) )"H( ) ) Q and H ( ) ) Q A ¸( ) ) A Q " Q . These relations are simple conclusions of the de"nitions of H ( ) ), H ( ) ), and H ( ) ). 2. We show that im Q ( ) )-kerA ( ) ). Regarding A C ( ) ) AH ( ) )"P , Q H ( ) )"H ( ) ) Q , di( ) ) dj " di ( ) ) dj PM< }C this holds trivially. 3. We show that kerA ( ) )-im Q ( ) ). Assume z3ker A ( ) ). Then, A C ( ) ) A z # A G( ) ) A Q z # A di( ) ) de Q z # A z # A di( ) ) dj z " 0, (64) !A Q z # ¸( ) ) z " 0, (65) A Q z " 0. (66) STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 157 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

Considering Equation (66) we see that z " Q <}C z . (67) Next, we have (cf. Equations (20), (21), and (23)) A di ( ) ) de Q z " 0, A di ( ) ) d j z " 0, (68) QA di ( ) ) de Q z " 0, Q A di ( ) ) dj z " 0, (69) Q<} C QA di ( ) ) de Q z " 0, Q<} C Q A di ( ) ) dj z " 0. (70) Multiplying Equation (64) by Q<} C Q yields Q<} C Q A G( ) ) A Q Q< }C z " 0. Since G( ) ) is positive de"nite and Equation (67) is valid, it holds that Q z " Q z . (71) Relation (65) leads to z " ¸ ( ) ) A Q z " ¸ ( ) ) A Q z . (72) Multiplying Equation (64) by Q yields now Q A z # QA di ( ) ) de Q z " 0. If we regard Equations (68)}(70), then relation (64) reduces to A C( ) ) A z # A di ( ) ) de Q z # A z " 0. (73) Since A (di ( ) )/de) Q " A C( ) ) A Q X( ) )#A A >( ) ), we obtain that QA di ( ) ) de "Q A A >( ) ). Multiplying Equation (73) by Q we conclude that Q A (A >( ) ) Q z # z )"0, i.e. A >( ) ) Q z # z " QM <}C (A >( ) ) Q z # z ). (74) From Equation (73) we obtain A C( ) ) Az # A C( ) ) A Q X ( ) ) Q z #A A >( ) ) Q z # A z " 0, 158 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

i.e. P (z # Q X ( ) ) Q z ) "!H( ) ) A (z # A >( ) ) Q z ) "!H ( ) ) A Q M< }C (z # A> ( ) ) Q z ) because of Equation (74). Thus, z"Q ( ) ) z # Q X ( ) ) Q z ¸ ( ) ) A Q z 0 3im Q ( ) ). 4. The relation S - ker Q ( ) ) is a simple conclusion of Equation (63). 5. We show that ker Q ( ) )-S . Assume Q ( ) ) z"0. Then ¸A Q H ( ) ) Q A z " 0 (75) and QM< }C H ( ) ) QM <} C A P z " 0. (76) Multiplying Equation (75) by Q A yields Q A z " 0. Regarding QM< }C H ( ) )"H ( ) ) QM< }C we conclude from Equation (75) that QM <} C A P z " 0. Considering Equation (63) the assertion is proved. Remark. Lemmas 6.2 and 6.5 now imply Theorem 6.1 for the tractability index. The validity of Theorem 4.2 follows by similar considerations as above. More precisely, it can be shown that the following relations are satis"ed for the charge-oriented MNA. (i) The analogue to Lemma 6.2 reads NS( ) )"im 0 0 0 0 0 0 0 0 0 0 0 0 Q 0 0 0 0 0 0 0 0 0 !PM <}C Z( ) ) Q 0 QM< }C for Z( ) ) chosen as in Lemma 6.2. STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 159 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

One exception is the one discussed in Lemma 6.2 and footnote . Straightforward computation shows that also N ( ) ) may change depending on the considered controlled sources. (ii) Lemma 6.4 reads im A ( ) )"ker Q 0 0 0 Q A ¸ ( ) ) 0 0 0 0 0 0 0 QM <} C QM <} CA H ( ) ) A 0 0 0 0 0 0 0 0 0 0 0 . (iii) Equation (63) corresponds to S ( ) )"ker QM< } C A H ( ) ) A ker Q A ¸ ( ) )n n n . (iv) Theorem 6.1 holds analogously for the charge-oriented MNA, and the canonical projector Q ( ) ) onto N ( ) ) along S ( ) ) is given by PM A H M A Q M< }C ) H ( ) ) QM <}C A H ( ) ) A !PM C ( ) ) A Q X( ) ) Q ) H( ) ) Q A ¸ ( ) ) 0 0 0 0 AQ H ( ) ) Q A ¸ ( ) ) 0 0 0 0 Q H ( ) ) Q A ¸ ( ) ) 0 0 0 0 0 0 0 0 !QM <}CH ( ) ) QM <} C A H ( ) ) A !A > ( ) ) Q H ( ) ) Q A ¸ ( ) ) 0 0 0 w here HM : " A A # Q Q and the matrices X( ) ) and >( ) ) are chosen as before. Note that if no controlled current sources that ful"l only the conditions (2b) or (2c) of Theorem 4.1 appear, then N is constant. 7. CONCLUSION The presented results provide information about the index of systems (6)}(8) and (9)}(13) by topological analysis of the network. The only assumption made on parameters is the mentioned positive de"niteness. The class of controlled sources described in the paper is precisely the one that does not seriously a!ect the structure of the spaces associated with the DAE-systems. Basically, these spaces are the same as for networks without controlled sources. If the class of controlled sources is not restricted then di!erent problems arise. 160 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

On the one hand, if arbitrary controlling elements for the controlling sources are considered then the index of the network equations may depend on the parameters (cf. Reference [22]). On the other hand, if controlled sources are allowed to form a part of ¸}I cutsets or C}< loops then it is possible to be confronted with higher index ('2) problems (cf. Reference [24]). ACKNOWLEDGEMENTS We would like to thank U. Feldmann of the Siemens AG Munich for the encouragement given. We are also indebted to R. MaKr z and R. Lamour for the helpful discussions. REFERENCES 1. Griepentrog E, MaKr z R. Di+erential}Algebraic Equations and ¹heir Numerical ¹reatment, Teubner-Texte zur Mathematik No. 88, BSB B.G. Teubner Verlagsgesellschaft, Leipzig, 1986. 2. Brenan KE, Campbell SL, Petzold LR. ¹he Numerical Solution of Initial <alue Problems in Ordinary Di+eren- tial}Algebraic Equations, North-Holland: Amsterdam, 1989. 3. Hairer E, Wanner G. Solving Ordinary Di+erential Equations II: Sti+ and Di+erential}Algebraic Problems, Springer Series in Computational Mathematics, Vol. 14. Springer: Berlin, Heidelberg, 1991. 4. Bryant PR. The order of complexity of electrical networks. Proceedings of the IEE (GB), Part C 1959; 106:174}188. 5. Rei{ig G. Extension of the normal tree method. International Journal of Circuit ¹heory and Applications 1999; 27:241}265. 6. Brayton RK, Moser JK. A theory of nonlinear networks I, II. Quarterly of Applied Mathematics 1964; 22:1}33, 81}104. 7. Chua LO, Rohrer RA. On the dynamic equations of a class of nonlinear RLC-networks. IEEE ¹ransactions Circuit ¹heory 1965; 12:475}489. 8. Kuh ES, Rohrer RA. The state-variable approach to network analysis. Proceedings of the IEEE 1965; 53:672}686. 9. Ohtsuki T, Watanabe H. State-Variable Analysis of RLC Networks Containing Nonlinear Coupling Elements. IEEE ¹ransaction Circuit ¹heory 1969; 16:26}38. 10. Chua LO, Lin P-M. Computer-Aided Analysis of Electronic Circuits. Prentice-Hall: Englewood Cli!s; NJ, 1975. 11. Matsumoto T. On the Dynamics of Electrical Networks. Journal of Di+erential Equations, 1976; 21:179}196. 12. Szatkowski A. On the dynamic spaces and on the equations of motion of non-linear RLC networks. International Journal of Circuit ¹heory Applications 1982; 10:99}122. 13. Haggman BC, Bryant PR. Solutions of singular constrained di!erential equations: a generalization of circuits containing capacitor-only loops and inductor-only cutsets. IEEE ¹ransactions on CAS 1984; 31:1015}1029. 14. Nishi T, Chua LO. Topological criteria for nonlinear resistive circuits containing controlled sources to have a unique solution. IEEE ¹ransactions on Circuits and Systems 1984; 31(8):722}741. 15. Hasler M. Non-linear non-reciprocal resistive circuits with a structurally unique solution. International Journal of Circuits ¹heory and Applications 1986; 14:237}262. 16. Mathis W. ¹heorie nichtlinearer Netzwerke, Springer: Berlin, Heidelberg, New York, 1987. 17. FosseHp rez M. Non-linear Circuits: Qualitative Analysis of Non-linear, Non-Reciprocal Circuits, Wiley: Chichester, 1992. 18. GuKn ther M, Feldmann U. The DAE-index in electric circuit simulation. Mathematics and Computers in Simulation 1995; 39:573}582. 19. GuKn ther M, Rentrop P. The di!erential}algebraic index concept in electric circuit simulation. Zeitschrift fuKr Angewandte Mathematik und Mechanik, 1996; 76(Suppl. 1):91}94. 20. Tischendorf C. Solution of index-2 di!erential algebraic equations and its application in circuit simulation. Ph.D. ¹hesis, Humboldt-University, Berlin, 1996. 21. MaKr z R, Tischendorf C. Recent results in solving index 2 di!erential algebraic equations in circuit simulation. SIAM Journal of Scienti,c and Statistical Computing 1997; 18(1):139}159. 22. Rei{ig G. BeitraKg e zu Theorie und Anwendung impliziter Di!erentialgleichungen, Ph.D. ¹hesis, Technical University, Dresden, 1998. 23. GuKn ther M, Feldmann U. CAD based electric modeling in industry. Part I : mathematical structure and index of network equations. Surveys on Mathematics for Industry 1999; 8:97}129. 24. GuKn ther M, Feldmann U. CAD based electric modeling in industry. Part II: Impact of circuit con"gurations and parameters. Surveys on Mathematics for Industry 1999; 8:131}157. 25. Tischendorf, C. Topological index calculation of DAEs in circuit simulation, Surveys on Mathematics for Industry 1999: 8:187}199. STRUCTURAL ANALYSIS OF ELECTRIC CIRCUITS 161 Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162

26. Rei{ig G. The index of the standard circuit equations of passive RLCTG-networks does not exceed 2. Proceedings of the ISCAS198, vol. 3. 1998; 419}422. 27. EsteHv ez Schwarz D. Topological analysis for consistent initialization in circuit simulation. ¹echnical Report 99-3, Fachbereich Mathematik, Humboldt-University, Berlin, 1999. 28. EsteHv ez Schwarz D. Consistent initialization of di!erential-algebraic equations in circuit simulation. ¹echnical Report 99-5, Fachbereich Mathematik, Humboldt-University, Berlin, 1999. 162 D. ESTEDV EZ SCHWARZ AND C. TISCHENDORF

  1. Ma K rz R, RodrıH guez Santiesteban AR. Analyzing the stability behaviour of DAE solutions and their approximations.
29. MaKr z R, RodrıH guez Santiesteban AR. Analyzing the stability behaviour of DAE solutions and their approximations.
¹echnical Report 99-2, Fachbereich Mathematik, Humboldt-University, Berlin, 1999.
30. Desoer C, Kuh E. Basic Circuit ¹heory, McGraw-Hill: Singapore, 1969.
31. Shichman H, Hodges DA. Insulated-gate "eld-e!ect transistor switching circuits. IEEE Journal of Solid State Circuits
1968; SC-3:285}289.
32. MaKr z R. Numerical methods for di!erential-algebraic equations. Acta Numerica 1992: 141}198.
33. Rabier P, Rheinboldt W. A general existence and uniqueness theory for implicit di!erential}algebraic equations,
Di+erential and Integral Equations 1991; 4(3):563}582.
34. Reich S. Beitrag zur Theorie der Algebrodi!erentialgleichungen, Ph.D. ¹hesis, Technical University Dresden, 1990.
35. Hosny E, Nassef M, Sobhy M. Computer-aided analysis of non-linear lumped-distributed multiport networks. IEEE
International Symposium on Circuits and Systems, New York, 1992; 428}431.
Copyright 2000 John Wiley & Sons, Ltd. Int. J. Circ. ¹heor. Appl. 2000; 28:131}162