A factorization-based framework for passivity-preserving model reduction of RLC systems

ABSTRACT

We present a framework for passivity-preserving model reduction for RLC systems that includes, as a special case, the well-known PRIMA model reduction algorithm. This framework provides a new interpretation for PRIMA, and offers a qualitative explanation as to why PRIMA performs remarkably well in practice. In addition, the framework enables the derivation of new error bounds for PRIMA-like methods. We also show how the framework offers a systematic approach to computing reduced-order models that better approximate the original system than PRIMA, while still preserving passivity.

REFERENCES

• 1: B. Anderson and S. Vongpanitlerd. Network analysis and synthesis: a modern systems theory approach. Prentice Hall, 1973.
• 2: V. Balakrishnan, Q. Su, and C.-K. Koh. Efficient balance-and-truncate model reduction for large scale systems. In Proc. American Control Conf., pages 4746--4751, Arlington, VA, June 2001.
• 3: S. Boyd, L. El~Ghaoui, E. Feron, and V. Balakrishnan. Linear Matrix Inequalities in System and Control Theory, volume 15 of Studies in Applied Mathematics. SIAM, Philadelphia, PA, June 1994.
• 4: X. Chen and T. Wen. Positive realness preserving model reduction with hinfty norm error bounds. IEEE Trans. on Circuits and Systems - 1: Fundamental Theory and Applications, 42(1):23--29, 1995.
• 5: Shen Lin , John P. Lillis, Interconnect Analysis and Synthesis, John Wiley & Sons, Inc., New York, NY, 1999
• 6: E. Chiprout , M. Nakhla, Generalized moment-matching methods for transient analysis of interconnect networks, Proceedings of the 29th ACM/IEEE conference on Design automation, p.201-206, June 08-12, 1992, Anaheim, California, United States
• 7: P. Feldmann and R. W. Freund. Efficient linear circuit analysis by Pade approximation via the Lanczos process. IEEE Trans. Computer-Aided Design, 14:639--649, May 1995.
• 8: Bruce A Francis, A course of H∞0Econtrol theory, Springer-Verlag New York, Inc., New York, NY, 1986
• 9: R. W. Freund. Reduced-order modeling techniques based on Krylov subspaces and their use in circuit simulation. Technical Report 98-3-02, Numerical Analysis Manuscript, Bell Laboratories, Murray Hill, New Jersey, Feb. 1998.
• 10: K. Gallivan, E. Grimme, and P. V. Dooren. Pade approximation of large scale dynamic systems with Lanczos methods. In Proc. IEEE Conf. on Decision and Control, pages 443--448, Dec. 1994.
• 11: Michael Green , David J. N. Limebeer, Linear robust control, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 12: E. Grimme, K. Gallivan, V. de Clippel, and P. V. Dooren. Approximate solves in Krylov-based modeling methods. In Proc. IEEE Conf. on Decision and Control, pages 3849--3854, Dec. 1997.
• 13: Pavan K. Gunupudi , Michel S. Nakhla, Model-reduction of nonlinear circuits using Krylov-space techniques, Proceedings of the 36th ACM/IEEE conference on Design automation, p.13-16, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309854]
• 14: X. Huang. Pade Approximation of Linear(ized) Circuit Responses. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, 1990.
• 15: P. Lancaster and L. Rodman. Algebraic Riccati Equations. Oxford University Press, 1995.
• 16: Jing-Rebecca Li , Frank Wang , Jacob K. White, An efficient Lyapunov equation-based approach for generating reduced-order models of interconnect, Proceedings of the 36th ACM/IEEE conference on Design automation, p.1-6, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309848]
• 17: Jing-Rebecca Li , Jacob White, Efficient model reduction of interconnect via approximate system gramians, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.380-384, November 07-11, 1999, San Jose, California, United States
• 18: B. C. Moore. Principal component analysis in linear systems: Controllability, observability, and model reduction. IEEE Trans. Aut. Control, AC-26(1):17--32, Feb. 1981.
• 19: A. Odabasioglu, M. Celik, and L. T. Pileggi. PRIMA: Passive reduced-order interconnect macromodeling algorithm. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 17(8):645--654, 1998.
• 20: L. T. Pillage and R. A. Rohrer. Asymptotic waveform evaluation for timing analysis. IEEE Trans. Computer-Aided Design, 9:352--366, 1990.
• 21: L. Miguel Silveira , Mattan Kamon , Jacob White, Efficient reduced-order modeling of frequency-dependent coupling inductances associated with 3-D interconnect structures, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.376-380, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217558]
• 22: R. A. Smith. Matrix equation XA + BX = C. SIAM Journal on Applied Mathematics, 16(1):198--201, 1968.
• 23: Q. Su , V. Balakrishnan , C-K. Koh, Efficient Approximate Balanced Truncation of General Large-Scale RLC Systems via Krylov Methods, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.311, January 07-11, 2002
• 24: J. C. Willems. Least squares stationary optimal control and the algebraic Riccati equation. IEEE Trans. Aut. Control, AC-16(6):621--634, Dec. 1971.
• 25: K. Zhou. Remarks on stochastic model reduction. IEEE Trans. Aut. Control, 32(4):356--358, 1987.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms

Keywords:
RLC interconnect, factorization, large scale systems, model reduction, passivity preserving