Passivity-preserving model reduction via a computationally efficient project-and-balance scheme

ABSTRACT

This paper presents an efficient t o-stage project-and-balance scheme for passivity-preserving model order reduction. Orthogonal dominant eigenspace projection is implemented by integrating the Smith method and Krylov subspace iteration. It is followed by stochastic balanced truncation herein a novel method, based on the complete separation of stable and unstable invariant subspaces of a Hamiltonian matrix, is used for solving two dual algebraic Riccati equations at the cost of essentially one. A fast-converging quadruple-shift bulge-chasing SR algorithm is also introduced for this purpose. Numerical examples confirm the quality of the reduced-order models over those from conventional schemes.

REFERENCES

• 1: A. Odabasioglu, M. Celik, and L. T. Pileggi, "PRIMA: Passive reduced-order interconnect macromodeling algorithm," IEEE Trans. Computer-Aided Design vol.17, no.8, pp.645--654, Aug. 1998.
• 2: Z. Bai, P. M. Dewilde, and R. W. Freund, "Reduced-order modeling," Numerical Analysis Manuscript No. 02-4-13, Bell Laboratories Mar. 2002.
• 3: L. T. Pillage and R. A. Rohrer, "Asymptotic waveform evaluation for timing analysis," IEEE Trans. Computer-Aided Design vol.9, no.4, pp. 352--366, Apr. 1990.
• 4: P. Feldmann , R. W. Freund, Reduced-order modeling of large linear subcircuits via a block Lanczos algorithm, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.474-479, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217573]
• 5: K. Glover, "All optimal Hankel-norm approximation of linear multivariable systems and their L∞-error bounds," Int. J. Control vol.39, no.6, pp.1115--1193, June 1984.
• 6: B. Moore, "Principal component analysis in linear systems: Controllability, observability, and model reduction," IEEE Trans. Automat. Contr., vol.26, no.1, pp.17--32, Feb. 1981.
• 7: T. Penzl, "Algorithms for model reduction of large dynamical systems," Sonderforschungsbereich 393 Numerische Simulation auf massiv parallelen Rechnern, TU Chemnitz, 09107 Chemnitz, FRG, Tech. Rep. SFB393/99-40, 1999.
• 8: 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
• 9: Qing Su , Venkataramanan Balakrishnan , Cheng-Kok Koh, Algorithms for model reduction of large scale rlc systems, 2002
• 10: M. Green, "Balanced stochastic realizations," Linear Algebra Appl., vol.98, pp. 211--247, 1988.
• 11: X. Chen and J. T. Wen, "Positive realness preserving model reduction ith H∞ norm error bounds," IEEE Trans. Circuits Syst. I vol. 42, no.1, pp. 23--29, Jan. 1995.
• 12: J. R. Phillips, L. Daniel, and L. M. Silveira, "Guaranteed passive balancing transformations for model order reduction," IEEE Trans. Computer-Aided Design vol. 22, no. 8, pp. 1027--1041, Aug. 2003.
• 13: Q. Su , V. Balakrishnan , C.-K. Koh, A factorization-based framework for passivity-preserving model reduction of RLC systems, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513931]
• 14: 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
• 15: J. Li, "Model reduction of large linear systems via low rank system gramians," Ph.D. dissertation, Department of Mathematics, Massachusetts Institute of Technology, Sept. 2000.
• 16: Jiérâi Vlach , Kishore Singhal, Computer Methods for Circuit Analysis and Design, John Wiley & Sons, Inc., New York, NY, 1993
• 17: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 18: G. S. Ammar, P. Benner, and V. Mehrmann, "A multishift algorithm for the numerical solution of algebraic Riccati equations," Electr. Trans. Num. Anal., vol. 1, pp. 33--48, Sept. 1993.
• 19: P. Benner and H. Faßbender, "An implicitly restarted symplectic Lanczos method for the Hamiltonian eigenvalue problem," Linear Algebra and its Applications vol. 263, pp. 75--111, 1997.
• 20: A. Bunse-Gerstner and V. Mehrmann, "A symplectic QR like algorithm for the solution of the real algebraic Riccati equation," IEEE Trans. Automat. Contr., vol. 31, no. 12, pp. 1104--1113, Dec. 1986.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms

Keywords:
Riccati equation, SR algorithm, dominant eigenspace, model reduction, projection, stochastic balanced truncation