Reduction of large circuit models via low rank approximate gramians

Jing-Rebecca Li; Jacob White

International Journal of Applied Mathematics and Computer Science (2001)

  • Volume: 11, Issue: 5, page 1151-1171
  • ISSN: 1641-876X

Abstract

top
We describe a model reduction algorithm which is well-suited for the reduction of large linear interconnect models. It is an orthogonal projection method which takes as the projection space the sum of the approximate dominant controllable subspace and the approximate dominant observable subspace. These approximate dominant subspaces are obtained using the Cholesky Factor ADI (CF-ADI) algorithm. We describe an improvement upon the existing implementation of CF-ADI which can result in significant savings in computational cost. We show that the new model reduction method matches moments at the negative of the CF-ADI parameters, and that it can be easily adapted to allow for DC matching, as well as for passivity preservation for multi-port RLC circuit models which come from modified nodal analysis.

How to cite

top

Li, Jing-Rebecca, and White, Jacob. "Reduction of large circuit models via low rank approximate gramians." International Journal of Applied Mathematics and Computer Science 11.5 (2001): 1151-1171. <http://eudml.org/doc/207549>.

@article{Li2001,
abstract = {We describe a model reduction algorithm which is well-suited for the reduction of large linear interconnect models. It is an orthogonal projection method which takes as the projection space the sum of the approximate dominant controllable subspace and the approximate dominant observable subspace. These approximate dominant subspaces are obtained using the Cholesky Factor ADI (CF-ADI) algorithm. We describe an improvement upon the existing implementation of CF-ADI which can result in significant savings in computational cost. We show that the new model reduction method matches moments at the negative of the CF-ADI parameters, and that it can be easily adapted to allow for DC matching, as well as for passivity preservation for multi-port RLC circuit models which come from modified nodal analysis.},
author = {Li, Jing-Rebecca, White, Jacob},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {Lyapunov equations; moment matching; passivity; model reduction; Cholesky-Factor ADI; Lyapunov equation; Cholesky factors; ADI; DC component},
language = {eng},
number = {5},
pages = {1151-1171},
title = {Reduction of large circuit models via low rank approximate gramians},
url = {http://eudml.org/doc/207549},
volume = {11},
year = {2001},
}

TY - JOUR
AU - Li, Jing-Rebecca
AU - White, Jacob
TI - Reduction of large circuit models via low rank approximate gramians
JO - International Journal of Applied Mathematics and Computer Science
PY - 2001
VL - 11
IS - 5
SP - 1151
EP - 1171
AB - We describe a model reduction algorithm which is well-suited for the reduction of large linear interconnect models. It is an orthogonal projection method which takes as the projection space the sum of the approximate dominant controllable subspace and the approximate dominant observable subspace. These approximate dominant subspaces are obtained using the Cholesky Factor ADI (CF-ADI) algorithm. We describe an improvement upon the existing implementation of CF-ADI which can result in significant savings in computational cost. We show that the new model reduction method matches moments at the negative of the CF-ADI parameters, and that it can be easily adapted to allow for DC matching, as well as for passivity preservation for multi-port RLC circuit models which come from modified nodal analysis.
LA - eng
KW - Lyapunov equations; moment matching; passivity; model reduction; Cholesky-Factor ADI; Lyapunov equation; Cholesky factors; ADI; DC component
UR - http://eudml.org/doc/207549
ER -

References

top
  1. Chandrasekharan P.C. (1996): Robust Control of Linear Dynamical Systems. — London: Harcourt Brace. 
  2. Ellner N.S. and Wachspress E.L. (1991): Alternating direction implicit iteration for systems with complex spectra. — SIAM J. Numer. Anal., Vol.28, No.3, pp.859–870. Zbl0737.65027
  3. Enns D.F. (1984): Model reduction with balanced realizations: An error bound and frequency weighted generalizations. — Proc. 23rd Conf. Decision and Control, Las Vegas, NV, pp.127–132. 
  4. Feldmann P. and Freund R. (1995): Efficient linear circuit analysis by Padé approximation via the Lanczos process. — IEEE Trans. Comp. Aided Des. Int. Circ. Syst., Vol.14, No.5, pp.639–649. 
  5. Freund R.W. (1993a): The look-ahead Lanczos process for large nonsymmetric matrices and related algorithms, In: Linear Algebra for Large Scale and Real-Time Applications (M.S. Moonen, G.H. Golub, B.L.R. de Moor, Eds.). — Dordrecht: Kluwer, pp.137–163. 
  6. Freund R.W. (1993b): Solution of shifted linear systems by quasi-minimal residual iterations, In: Numerical Linear Algebra (L. Reichel, A. Ruttan, R.S. Varga, Eds.). — Berlin: de Gruyter, pp.101–121. Zbl0794.65028
  7. Freund R.W. (1999): Reduced-order modeling techniques based on Krylov subspaces and their use in circuit simulation, In: Applied and Computational Control, Signals, and Circuits, Vol. 1 (B.N. Datta, Ed.). — Boston: Birkhäuser, pp.435–498. Zbl0967.93008
  8. Gallivan K., Grimme E. and van Dooren P. (1994): Asymptotic waveform evaluation via a Lanczos method. — Appl. Math. Lett., Vol.7, No.5, pp.75–80. Zbl0810.65067
  9. Gallivan K., Grimme E. and van Dooren P. (1996a): A rational Lanczos algorithm for model reduction. — Numer. Algorithms, Vol.12, No.1–2, pp.33–63. Zbl0870.65053
  10. Gallivan K., Grimme E., Sorensen D. and van Dooren P. (1996b): On some modifications of the Lanczos algorithm and the relation with Padé approximations, In: ICIAM 95 (K. Kirchgässner, O. Mahrenholtz, R. Mennicken, Eds.). — Berlin: Akademie Verlag, pp.87–116. Zbl1075.93506
  11. Glover K. (1984): All optimal Hankel-norm approximations of linear multivariable systems and their L∞ -error bounds. — Int. J. Contr., Vol.39, No.6, pp.1115–1193. Zbl0543.93036
  12. Golub G.H. and van Loan C.F. (1996): Matrix Computations, 3rd Ed. — Baltimore, MD: Johns Hopkins University Press. Zbl0865.65009
  13. Grimme E. (1997): Krylov projection methods for model reduction. — Ph.D. Thesis, University of Illinois at Urbana-Champaign. 
  14. Grimme E.J., Sorensen D.C. and van Dooren P. (1996): Model reduction of state space systems via an implicitly restarted Lanczos-method. — Numer. Algorithms, Vol.12, No.1–2, pp.1–31. Zbl0870.65052
  15. Li J.R. and White J. (1999): Efficient model reduction of interconnect via approximate system gramians. — Proc. IEEE/ACM Int. Conf. Computer-Aided Design, San Jose, CA, pp.380–383. 
  16. Li J.R., Wang F. and White J. (1999): An efficient Lyapunov equation-based approach for generating reduced-order models of interconnect. — Proc. 36th Design Automation Conf., New Orleans, LA, pp.1–6. 
  17. Lu A. and Wachspress E.L. (1991): Solution of Lyapunov equations by alternating direction implicit iteration. — Comput. Math. Appl., Vol.21, No.9, pp.43–58. Zbl0724.65041
  18. Marques N., Kamon M., White J. and Silveira L. (1998): A mixed nodal-mesh formulation for efficient extraction and passive reduced-order modeling of 3D interconnects. — Proc. 35th ACM/IEEE Design Automation Confer., San Francisco, CA, pp.297–302. 
  19. Miguel Silveira L., Kamon M., Elfadel I. and White J. (1996): A coordinate-transformed Arnoldi algorithm for generating guaranteed stable reduced-order models of RLC circuits. — Proc. IEEE/ACM Int. Conf. Computer-Aided Design, San Jose, CA, pp.288–294. Zbl0941.78013
  20. Moore B.C. (1981): Principal component analysis in linear systems: Controllability, observability, and model reduction. — IEEE Trans. Automat. Contr., Vol.26, pp.17–32. Zbl0464.93022
  21. Odabasioglu A., Celik M. and Pileggi L. (1998): PRIMA: Passive Reduced-order Interconnect Macromodeling Algorithm. — IEEE Trans. Comp. Aided Des. Int. Circ. Syst., Vol.17, No.8, pp.645–654. 
  22. Penzl T. (1999a): Algorithms for model reduction of large dynamical systems. — Tech. Rep., TU Chemnitz. Zbl1092.65053
  23. Penzl T. (1999b): A cyclic low-rank Smith method for large sparse Lyapunov equations. — SIAM J. Sci. Comput., Vol.21, No.4, pp.1401–1418 (electronic). Zbl0958.65052
  24. Pernebo L. and Silverman L.M. (1982): Model reduction via balanced state space representations. — IEEE Trans. Automat. Contr., Vol.27, No.2, pp.382–387. Zbl0482.93024
  25. Safonov M.G. and Chiang R.Y. (1989): A Schur method for balanced-truncation model reduction. — IEEE Trans. Automat. Contr., Vol.34, No.7, pp.729–733. Zbl0687.93027
  26. Sontag E.D. (1998): Mathematical Control Theory. — New York: Springer-Verlag. Zbl0945.93001
  27. Tombs M.S. and Postlethwaite I. (1987): Truncated balanced realization of a stable nonminimal state-space system. — Int. J. Contr., Vol.46, No.4, pp.1319–1330. Zbl0642.93015
  28. Wachspress E.L. (1995): The ADI Model Problem. — Windsor, CA. Zbl1277.65022

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.