Guaranteed stable projection-based model reduction for indefinite and unstable linear systems

ABSTRACT

In this work we present a stability-preserving projection framework for model reduction of linear systems. Specifically, given one projection matrix (e.g. a right-projection matrix), we derive a set of linear constraints for the other projection matrix (e.g. the left-projection matrix) resulting in a projection framework that is guaranteed to generate a stable reduced model. Several efficient techniques for solving the proposed system of constraints are presented, including an optimization problem formulation for finding the optimal stabilizing projection, and a formulation with computational complexity independent of the size of the original system. The resulting algorithms can create accurate stable and passive models of arbitrary indefinite systems at a significantly cheaper cost than existing methods such as balanced truncation. Nevertheless, our algorithms integrate fully and effortlessly with most of the available standard model order reduction approaches for very large systems generated in VLSI applications (such as moment-matching methods, POD, or Poor Man's TBR), which can guarantee stability and passivity only in very specialized cases. Our algorithms have been tested on a large variety of typical VLSI applications, including field-solver-extracted models of RF inductors for analog applications, power distribution grids for large VLSI digital integrated circuits, and MEMS devices for sensing and actuation applications. The results have been successfully compared to those from existing and much more expensive stabilizing reduction techniques.

REFERENCES

• 1: Eric Grimme. Krylov Projection Methods for Model Reduction. PhD thesis, Coordinated-Science Laboratory, University of Illinois at Urbana-Champaign, Urbana-Champaign, IL, 1997.
• 2: Zhaojun Bai, Peter Feldmann, and Roland W. Freund. Stable and passive reduced order models based on partial pade approximation via the lanczos process. Technical Report Numerical Analysis Manuscript No.97-3-10, Bell Laboratories, Lucent Technologies, Murray Hill, New Jersey, October 1997.
• 3: A. Odabasioglu, M. Celik, and L. T. Pileggi. PRIMA: passive reduced order interconnect macromodeling algorithm. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 17(8):645--654, August 1998.
• 4: Kevin J. Kerns , Ivan L. Wemple , Andrew T. Yang, Stable and efficient reduction of substrate model networks using congruence transforms, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.207-214, November 05-09, 1995, San Jose, California, United States
• 5: L. M. Silveira, M. Kamon, I. Elfadel, and J. K. White. Coordinate-transformed arnoldi algorithm for generating guarantee stable reduced-order models of RLC. Computer Methods in Applied Mechanics and Engineering, 169(3--4):377--89, February 1999.
• 6: Roland W. Freund, Krylov-subspace methods for reduced-order modeling in circuit simulation, Journal of Computational and Applied Mathematics, v.123 n.1-2, p.395-421, Nov. 2000 [doi>10.1016/S0377-0427(00)00396-4]
• 7: Bradley N Bond , Luca Daniel, Stabilizing schemes for piecewise-linear reduced order models via projection and weighting functions, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 8: Bruce Moore. Principal Component Analysis in Linear Systems: Controllability, Observability, and Model Reduction. IEEE Transactions on Automatic Control, AC-26(1):17--32, February 1981.
• 9: J. R. Phillips, L. Daniel, and M. Silveira. Guaranteed passive balancing transformations for model order reduction. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 22(8):1027--41, Aug 2003.
• 10: M. Vidyasagar, Nonlinear systems analysis (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 11: S. Sastry. Nonlinear Systems: Analysis, Stability, and Control. Springer, New York, 1999.
• 12: T. Stykel. Stability and inertia theorems for generalized lyapunov equations. Linear Algebra and its Applications, volume=.
• 13: J. C. Willems. Dissipative dynamical systems. Arch. Rational Mechanics and Analysis, 45:321--393, 1972.
• 14: Anders Rantzer. On the Kalman-Yakubovich-Popov lemma. Systems and Control Letters, 27(5), January 1996.
• 15: R. Freund and F. Jarre. An extension of the positive real lemma to descriptor systems. Technical Report Numerical Analysis Manuscript No.00-3-09, Bell Laboratories, Lucent Technologies, Murray Hill, New Jersey, December 2000.
• 16: Peter Feldmann , Roland W. Freund, Efficient linear circuit analysis by Pade´ approximation via the Lanczos process, Proceedings of the conference on European design automation, p.170-175, September 19-23, 1994, Grenoble, France
• 17: R. W. Freund and P. Feldmann. The SyMPVL algorithm and its applications to interconnect simulation. In Proceedings of the 1997 International Conference on Simulation of Semiconductor Processes and Devices, pages 113--116. IEEE, 1997.
• 18: K. Willcox and J. Peraire. Balanced model reduction via the proper orthogonal decomposition. In Proceedings of the 15th AIAA Computational Fluid Dynamics Conference, Anaheim, CA, June 2001.
• 19: Joel Phillips , L. Miguel Silveira, Poor Man's TBR: A Simple Model Reduction Scheme, Proceedings of the conference on Design, automation and test in Europe, p.20938, February 16-20, 2004
• 20: J. F. Sturm. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 11--12:625--653, 1999.
• 21: J. Lfberg. Yalmip: A toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.
• 22: Tarek Moselhy , Xin Hu , Luca Daniel, pFFT in FastMaxwell: a fast impedance extraction solver for 3D conductor structures over substrate, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 23: Fastmaxwell. http://www.rle.mit.edu/cpg/fastmaxwell.
• 24: S. D. Senturia E. Hung, Y.-J. Yahg. Low-order models for fast dynamical simulation of mems microstructures. In Proceedings of IEEE International Conference on Solid State Sensors and Actuators, volume 2, pages 1101--1104, 1997.