No Access

The Minimum Norm Least-Squares Solution in Reduction by Krylov Subspace Methods

Xinsheng Wang

School of Astronautics, Harbin Institute of Technology, 92 West Dazhi Street, Harbin, Heilongjiang 150001, P. R. China

E-mail Address: xswang@hit.edu.cn

Corresponding author.

Search for more papers by this author

Chenxu Wang

International Microelectronics Laboratory, West Culture Road, Weihai, Shandong 264209, P. R. China

E-mail Address: express@hitwh.edu.cn

Search for more papers by this author

, and

Mingyan Yu

School of Astronautics, Harbin Institute of Technology, 92 West Dazhi Street, Harbin, Heilongjiang 150001, P. R. China

E-mail Address: myyu@hit.edu.cn

Search for more papers by this author

https://doi.org/10.1142/S0218126617500062Cited by:1 (Source: Crossref)

Abstract

In recent years, model order reduction (MOR) of interconnect system has become an important technique to reduce the computation complexity and improve the verification efficiency in the nanometer VLSI design. The Krylov subspaces techniques in existing MOR methods are efficient, and have become the methods of choice for generating small-scale macro-models of the large-scale multi-port RCL networks that arise in VLSI interconnect analysis. Although the Krylov subspace projection-based MOR methods have been widely studied over the past decade in the electrical computer-aided design community, all of them do not provide a best optimal solution in a given order. In this paper, a minimum norm least-squares solution for MOR by Krylov subspace methods is proposed. The method is based on generalized inverse (or pseudo-inverse) theory. This enables a new criterion for MOR-based Krylov subspace projection methods. Two numerical examples are used to test the PRIMA method based on the method proposed in this paper as a standard model.

This paper was recommended by Regional Editor Emre Salman.

Keywords:

References

1. L. T. Pillage and R. A. Rohrer, Asymptotic waveform evaluation for timing analysis, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 9 (1990) 352–366. Crossref, Web of Science, Google Scholar
2. P. Feldmann and R. W. Freund, Efficient linear circuit analysis by Pade approximation via the Lanczos process, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 14 (1995) 639–649. Crossref, Web of Science, Google Scholar
3. A. Odabasioglu, M. Celik and L. Pileggi, PRIMA: Passive reduced-order interconnect macromodeling algorithm, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 17 (1998) 645–654. Crossref, Web of Science, Google Scholar
4. B. C. Moore, Principal component analysis in linear systems: Controllability, observability and model reduction, IEEE Trans. Autom. Control 26 (1981) 17–32. Crossref, Web of Science, Google Scholar
5. R. W. Freund and P. Feldmann, Reduced-order modeling of large linear subcircuits via a block Lanczos algorithm, Proc. Design Automation Conf., San Francisco, California (1995), pp. 474–479. Google Scholar
6. R. W. Freund and P. Feldmann, Reduced-order modeling of large linear subcircuits by means of the SyPVL algorithm, Proc. IEEE/ACM Int. Conf. Computer Aided Design, San Jose, CA (1996), pp. 280–287. Google Scholar
7. M. Silveira, M. Kamon, I. Elfadel and J. White, 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 (1996), pp. 288–294. Google Scholar
8. M. Silveira, M. Kamon and J. White, Efficient reduced-order modeling of frequency-dependent coupling inductances associated with 3-D interconnect structures, IEEE Transaction on Components, Packaging, and Manufacturing Technology-Part B, Vol 19, No. 2, 1996, pp. 283–288. Google Scholar
9. J. Cong, L. He, C. K. Koh and P. Padden, Performance optimization of VLSI interconnect layout, Integr. VLSI J. 21 (1996) 81–94. Crossref, Web of Science, Google Scholar
10. J. Lillis, C. Cheng, S. Lin and N. Chang, Interconnect Analysis and Synthesis (John Wiley and Sons, Hoboken, 1999). Google Scholar
11. N. Deo, Graph Theory with Application to Engineering and Computer Science (Prentice-Hall, Englewood Cliffs, 1974). Google Scholar
12. L. T. Pillage, R. A. Rohrer and C. Visweswariah, Electronic Circuit and System Simulation Methods (McGraw-Hill, New York, 1995). Google Scholar
13. A. E. Ruehli, Circuit Analysis, Simulation and Design: Part 1: General Aspects of Circuit Analysis and Design (North-Holland, Amsterdam, 1986). Google Scholar
14. J. Vlach and K. Singhal, Computer Methods for Circuit Analysis and Design, 2nd edn. (Van Nostrand-Reinhold, New York, 1994). Google Scholar
15. W. E. Arnoldi, The principle of minimized iteration in the solution of the matrix eigenvalue problem, Q. Appl. Math. 9 (1951) 17–29. Crossref, Web of Science, Google Scholar
16. R. W. Freund, Passive reduced order modeling of interconnects simulation and their computation by Krylov-subspace algorithm, Proc. 36th Design Automation Conf., New Orleans, LA (1999), pp. 195–200. Google Scholar
17. Y. Saad, Iterative Methods for Sparse Linear System (PWS, Boston, 2000). Google Scholar
18. B. Salimbahrami and B. Lohmann, Krylov subspace methods in linear model order reduction: Introduction and invariance properties, Technical Report, Institute of Automation, University of Bremen (2002). Google Scholar
19. M. Celik, L. Pileggi and A. Odabasioglu, IC Interconnect Analysis (Kluwer Academic, Cambridge, 2002). Google Scholar
20. G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd edn. (Johns Hopkins University Press, Baltimore, 1996). Google Scholar
21. S. L. Campbell and C. D. Meyer, Generalized Inverses of Linear Transformations (Pitman, London, 1979). Google Scholar
22. A. Ben-Israel and T. N. E. Grenville, Generalized Inverses: Theory and Applications (Springer-Verlag, Berlin, 2002). Google Scholar
23. F. Toutounian and A. Ataei, A new method for computing Moore–Penrose inverse matrices, J. Comput. Appl. Math. 228 (2009) 412–417. Crossref, Web of Science, Google Scholar
24. V. N. Katsikis, An improved method for the computation of the Moore–Penrose inverse matrix, Appl. Math. Comput. 217 (2011) 9828–9834, arXiv:1102.1845v1 [math.NA]. Web of Science, Google Scholar
25. University of Freiburg, Oberwolfach Model Reduction Benchmark Collection (2013), http://portal.uni-freiburg.de/imteksimulation/downloads/benchmark. Google Scholar
26. J. M. Wang, C.-C. Chu, Q. Yu and E. S. Kuh, On projection-based algorithms for model-order reduction of interconnects, IEEE Trans. Circuits Syst. I 49 (2002) 1563–1585. Crossref, Google Scholar
27. M. Kamon, M. J. Tsuk and J. White, Fasthenry: A multipole-accelerated 3-D inductance extraction program, IEEE Trans. Microw. Theory Tech. 42 (1994) 1750–1758. Crossref, Web of Science, Google Scholar