Advanced Non-Krylov Subspace Model Order Reduction Techniques for Interconnect Circuits

Model order reduction (MOR) is an efficient technique to reduce the complexity of dynamical systems while producing a good approximation of the input and output behavior. Classical MOR approaches such as Krylov subspace and truncated balanced realization methods have been well developed in the areas of system, control, and applied math for general systems in state-space equations. In recent years, MOR techniques using Krylov subspace algorithm have been studied intensively in the field of electronic design automation (EDA) for interconnect analysis. Interconnects in integrated circuits (IC) can be extracted as RLC circuits, which are described by a class of state-space equations with special structure properties such as symmetry, positive semi-definiteness and sparsity. As a result, to reduce the complexity of interconnect circuits, we can take advantage of the special structures to simplify the classical MOR methods. On the other hand, there are also some special requirements for interconnect reduction: scalability to large problems, passivity and structure preserving, and application to circuits with massive ports. In this thesis, we present several non-Krylov subspace MOR techniques for interconnect analysis.First, we present new methods based on classical balanced truncation for interconnect analysis: we generalize the simultaneous diagonalization algorithm for first-order balanced truncation to overcome the high computing costs; we also propose a passive second-order balanced truncation technique (and its fast version) to preserve both passivity and structure information inherent to circuit formulation. Second, we propose two new methods to perform passive reduction: we present new algorithm based on the Caratheodory extension, which has a similar computational cost as the Krylov subspace based methods but ensures the passivity of reduced model without any restriction on the internal structure of state-space equation; we also propose the concept of conditional passivity and a method to generate frequency band-limited passive reduced models.Finally, we work on long-standing problem of reducing interconnect circuits with massive ports. We propose a decentralized MOR scheme, where a multi-input multi-output (MIMO) system is decoupled into a number of subsystems in terms of outputs. The decoupling process and terminal reduction are based on the relative gain array (RGA), which measures the degree of interaction of each input-output pair. The reduction scheme can lead to passive reduction and is suitable for resistive coupling dominatant networks like power grids and substrate networks