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.
@article{bwmeta1.element.bwnjournal-article-amcv11i5p1151bwm,
author = {Li, Jing-Rebecca and White, Jacob},
title = {Reduction of large circuit models via low rank approximate gramians},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {11},
year = {2001},
pages = {1151-1171},
zbl = {0995.93027},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv11i5p1151bwm}
}
Li, Jing-Rebecca; White, Jacob. Reduction of large circuit models via low rank approximate gramians. International Journal of Applied Mathematics and Computer Science, Tome 11 (2001) pp. 1151-1171. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv11i5p1151bwm/
[000] Chandrasekharan P.C. (1996): Robust Control of Linear Dynamical Systems. — London: Harcourt Brace.
[001] 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. | Zbl 0737.65027
[002] 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.
[003] 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.
[004] 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.
[005] 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. | Zbl 0794.65028
[006] 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. | Zbl 0967.93008
[007] 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. | Zbl 0810.65067
[008] 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. | Zbl 0870.65053
[009] 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. | Zbl 1075.93506
[010] 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. | Zbl 0543.93036
[011] Golub G.H. and van Loan C.F. (1996): Matrix Computations, 3rd Ed. — Baltimore, MD: Johns Hopkins University Press. | Zbl 0865.65009
[012] Grimme E. (1997): Krylov projection methods for model reduction. — Ph.D. Thesis, University of Illinois at Urbana-Champaign.
[013] 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. | Zbl 0870.65052
[014] 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.
[015] 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.
[016] 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. | Zbl 0724.65041
[017] 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.
[018] 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. | Zbl 0941.78013
[019] Moore B.C. (1981): Principal component analysis in linear systems: Controllability, observability, and model reduction. — IEEE Trans. Automat. Contr., Vol.26, pp.17–32. | Zbl 0464.93022
[020] 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.
[021] Penzl T. (1999a): Algorithms for model reduction of large dynamical systems. — Tech. Rep., TU Chemnitz. | Zbl 1092.65053
[022] 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). | Zbl 0958.65052
[023] 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. | Zbl 0482.93024
[024] 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. | Zbl 0687.93027
[025] Sontag E.D. (1998): Mathematical Control Theory. — New York: Springer-Verlag. | Zbl 0945.93001
[026] 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. | Zbl 0642.93015
[027] Wachspress E.L. (1995): The ADI Model Problem. — Windsor, CA. | Zbl 1277.65022