Kron Reduction of Graphs with Applications to Electrical ...

1 1 Kron Reduction of Graphs with Applications toElectrical NetworksFlorian D orfler Francesco BulloAbstract Consider a weighted undirected graph and its corre-sponding Laplacian matrix, possibly augmented with additionaldiagonal elements corresponding to self-loops. The Kron reduc-tion of this graph is again a graph whose Laplacian matrix is ob-tained by the Schur complement of the original Laplacian matrixwith respect to a specified subset of nodes. The Kron reductionprocess is ubiquitous in classic circuit theory and in relateddisciplines such as Electrical impedance tomography, smart gridmonitoring, transient stability assessment, and analysis of powerelectronics. Kron Reduction is also relevant in other physicaldomains, in computational Applications , and in the reductionof Markov chains.

2 Related concepts have also been studied aspurely theoretic problems in the literature on linear this paper we analyze the Kron Reduction process from theviewpoint of algebraic graph theory. Specifically, we providea comprehensive and detailed graph -theoretic analysis of Kronreduction encompassing topological, algebraic, spectral, resistive,and sensitivity analyses. Throughout our theoretic elaborationswe especially emphasize the practical applicability of our resultsto various problem setups arising in engineering, computation,and linear algebra. Our analysis of Kron Reduction leads to novelinsights both on the mathematical and the physical Terms Kron Reduction , equivalent circuit, algebraicgraph theory, Ward equivalent, network -reduced modelI.

3 INTRODUCTIONC onsider an undirected, connected, and weighted graph withnnodes and adjacency matrixA Rn n. The correspondingloopy Laplacian matrix is the matrixQ Rn nwith off-diagonal elementsQij= Aijand diagonal elementsQii=Aii+ nj=1 Aij. Consider now a simple algebraic operation,namely the Schur complement of the loopy Laplacian matrixQwith respect to a subset of nodes. As it turns out, the resultinglower dimensional matrixQredis again a well-defined loopyLaplacian matrix, and a graph can be naturally associated to paper investigates this Schur complementation fromthe viewpoint of algebraic graph theory. In particular we seekanswers to the following questions. How are the spectrum andthe algebraic properties ofQandQredrelated? How about thecorresponding graph topologies and the effective resistances?

4 What is the effect of a perturbation in the original graph onthe reduced graph , its loopy LaplacianQred, its spectrum, andits effective resistance? Finally, why is this graph reductionprocess of practical importance and in which applicationareas? These are some of the questions that motivate this networks and the Kron illustratethe physical dimension of the problem setup introduced above,This material is based in part upon work supported by NSF grants IIS-0904501 and D orfler and Francesco Bullo are with the Center forControl, Dynamical Systems and Computation, University of Cali-fornia at Santa Barbara, Santa Barbara, CA consider the circuit naturally associated to the adjacencymatrixA.

5 Consider a connected Electrical network withnnodes, current injectionsI Rn 1, nodal voltagesV Rn 1,branch conductancesAij 0, and shunt conductancesAii 0connecting nodeito the ground. The resulting current-balance equations areI=QV, where the conductance matrixQ Rn nis the loopy Laplacian. In circuit theory andrelated disciplines it is desirable to obtain a lower dimensionalelectrically-equivalent network from the viewpoint of certainboundary nodes ({1,..,n},| | 2. If ={1,..,n}\ denotes the interior nodes, then, after appropriately labelingthe nodes, the current-balance equations can be partitioned as[I I ]=[Q Q Q Q ][V V ].(1)Gaussian elimination of the interior voltagesV in equations(1) gives an electrically-equivalent reduced network with thenodes obeying the reduced current-balance equationsI +QacI =QredV ,(2)where the reduced conductance matrixQred R| | | |isgiven by the Schur complement ofQwith respect to theinterior nodes , that is,Qred=Q Q Q 1 Q , and theaccompanying matrixQac= Q Q 1 R| | (n | |)mapsinternal currents to boundary currents in the reduced Reduction of an Electrical network via a Schur comple-ment of the associated conductance matrix is known asKronreductiondue to the seminal work of Gabriel Kron [1].)

6 In caseof a star-like network without interior current injections andshunt conductances, the Kron Reduction of a network reducesto the (generalized) star-triangle transformation [2], [3].Literature Kron Reduction of networks isubiquitous in circuit theory and related Applications in orderto obtain lower dimensional electrically-equivalent circuits. Itappears for instance in the behavior, synthesis, and analysis ofresistive circuits [4] [6], particularly in the context of large-scale integration chips [7], [8]. When applied to the impedancematrix of a circuit rather than the admittance matrix, Kronreduction is also referred to as the shortage operator [9],[10]. Kron Reduction is a standard tool in the power systemscommunity to obtain so-called network -reduced or Ward-equivalent models for power flow studies [11], [12], toreduce differential-algebraic power network models to purelydynamic models [13] [16], and it is crucial for reduced ordermodeling, analysis, and efficient simulation of induction mo-tors [17] and power electronics [18], [19].

7 A recent applicationof Kron Reduction is monitoring in smart power grids [20]via synchronized phasor measurement units. Kron reduction2is also known in the literature on Electrical impedance tomog-raphy, whereQredis referred to as the Dirichlet-to-Neumannmap [21] [23]. More generally, the Schur complement ofa matrix and its associated graph is known in the contextof Gaussian elimination of sparse matrices [24] [26] and itsapplication to Laplacian matrices can be found, for example,in sparse multi-grid solvers [27] and in finite-element analysis[17]. It serves as popular application example in linear algebra[28] [31], a similar concept is employed in the cyclic reduc-tion [32] or the stochastic complement [33] of Markov chains,and a related concept is the Perron complement [34], [35] ofa matrix and its associated graph with Applications in datamining [36].

8 Finally, Kron Reduction is also crucial in modelreduction of water supply networks [37] and in the context ofthe Yang-Baxter equation and its Applications in knot theory,high-energy physics, and statistical mechanics [38].This brief literature review shows that Kron Reduction isboth a practically important and theoretically fascinating prob-lem occurring in numerous Applications . Each of the aforemen-tioned communities has different approaches and insights intoKron Reduction . Engineers understand the physical dimensionof Kron Reduction very well, the computation communityinvestigates the sparsity pattern of the Kron-reduced matrix,and the linear algebra community is interested in eigenvalueproblems. Surprisingly, across different scientific communitieslittle is known about the graph -theoretic properties of theKron Reduction process.

9 Yet the graph -theoretic analysis ofKron Reduction provides novel and deep insights both on themathematical and the physical side of the considered this paper we provide a detailed andcomprehensive graph -theoretic analysis of the Kron reductionprocess. Our general graph -theoretic framework and analysisof Kron Reduction encompasses various theoretical problemsetups as well as practical Applications in a unified , Kron Reduction of a connected graph , possiblywith self-loops, is a Schur complement of corresponding loopyLaplacian matrix with respect to a subset of nodes. We relatethe topological, the algebraic, and the spectral properties of theresulting Kron-reduced Laplacian matrix to those of the non-reduced Laplacian matrix. Furthermore, we relate the effectiveresistances in the original graph to the elements and effectiveresistances induced by the Kron-reduced Laplacian.

10 Thereby,we complement and extend various results in the literatureon the effective resistance of a graph [10], [39] [42]. Inour analysis, we carefully analyze the effects of self-loops,which typically model loads and dissipation. We also presenta sensitivity analysis of the algebraic, spectral, and resistiveproperties of the Kron-reduced matrix with respect to per-turbations in the non-reduced network topology. Finally, ouranalysis of Kron Reduction complements the literature in linearalgebra [28] [31], and we construct an explicit relationship toanalogous results on the Perron complement side [33] [36]such that our results apply also to Markov chain the paper, we will remark whenever certain basiclemmas are known or partially known to some our analysis we do not aim at deriving only mathematicalelegant results but also useful tools for practical general graph -theoretic framework encompasses the appli-cations of Kron Reduction in circuit theory [4] [8], electricalimpedance tomography [21] [23], sensitivity in power flowstudies [11], [12], monitoring in smart grids [20], transient sta-bility assessment in power grids [13] [16]