A fast wavelet collocation method for high-speed VLSI circuit simulation

ABSTRACT

This paper presents a fast wavelet collocation method (FWCM) for high- speed circuit simulation. The FWCM has the following properties: (1) It works in the time domain, so that the circuit nonlinearity can be handled, and the accuracy of the result can be well controlled, unlike the method working in the frequency domain where the numerical error may get uncontrolled during the inverse Laplace transform; (2) The wavelet property of localization in both time and frequency domains makes a uniform approximation possible, which is generally not found in the time marching methods; (3) It is very effective in treating the singularities often developed in high-speed ICs due to the property of the wavelets; (4) Calculation of derivatives at all collocation points is optimal and takes O(n\log n), where n is the number of collocation points; (5) An adaptive scheme exists; and (6) It has an O(h^4) convergence rate while the most existing methods only have an O(h^2) convergence rate, where h is the step length. Numerical experiments further demonstrated the promising features of FWCM in high-speed IC simulation.

REFERENCES

• 1: R.L. Burden and J. D. Faires, Numerical Analysis, PWS Publishing Company, 1993.
• 2: Leon O. Chua , Paul Y. Lin, Computer-Aided Analysis of Electronic Circuits: Algorithms and Computational Techniques, Prentice Hall Professional Technical Reference, 1975
• 3: L.T. Pillage and R.A. Rohrer, it Asymptotic Waveform Evaluation for Timing Analysis, IEEE Trans. on CAD", Vol. 9, Number 4, pp.352-366, 1990.
• 4: R. Glowinski, A. Rieder, R. O. Wells, Jr., and X. Zhou, A wavelel mullilevel melhod for Dirichlel boundary value problems in general domains. Technical Report 93-06, Rice University, 1993. Computational Mathematics Laboratory.
• 5: E.Bacry, S. Mallat and G. Papanicolaou, A wavelel based space-lime adaplive numerical melhod for parlial differenlial equalions, Technical Report No 591, Robotics Report No 257, New York University, Courant Institute of Mathematical Sciences, Nov.1991.
• 6: G. Beylkin, On wavelel-based algorilhm for solving differenlial equalions, preprint, 1992.
• 7: L. Greengard and V. Rokhlin, On lhe numerical solulion of lwo-poinl boundary value problems, Yale University Technical Report, YALEU/DCS/RR-692 (1989)
• 8: Stephane Jaffard, Wavelet methods for fast resolution of elliptic problems, SIAM Journal on Numerical Analysis, v.29 n.4, p.965-986, Aug. 1992 [doi>10.1137/0729059]
• 9: J.-C. Xu and W.-C. Shann, Galerkin-wavelel melhods for lwo poinl boundary value problems. Numer. Math., 63(1):123-142, 1992.
• 10: I. Daubechies, Orlhogonal bases of compactly supported wavelets, Comm. Pure Appl. Math. 41 (1988), pp. 909-996.
• 11: Y. Meyer, Ondelelles gl opglaleurs, I: Ondelettes. Hermann, Paris 1990
• 12: Charles K. Chui, An introduction to wavelets, Academic Press Professional, Inc., San Diego, CA, 1992
• 13: A. Cohen, I. Daubechies, and P. Vial, Wavelets on the interval and fast wavelet transforms, Submitted to Applied and Computational Harmonic Analysis.
• 14: Y. Meyer, Ondelelles sur l'inlervalle, Rev. Mat. Iberoamericana, 7 (1991), 115-143.
• 15: C.K. Chui, E. Quak, Wavelets on a bounded interval, CAT Report 265, Department of Mathematics, Texas A L; M University, March, 1992.
• 16: A. Harten, Mulliresolulion Represenlalion of Data, Courant Mathematics and Computing Laboratory report No. 93-002, June, 1993.
• 17: J.Z.Wang, Construction of wavelet bases in Sobolev spaces on a finite interval, Report on 1992 Summer Research conference of AMS "wavelets and applications," South Hadley, July, 1992.
• 18: G. Beylkin, Wavelets, Mulliresolulion Analysis and Fast Numerical Algorithms. A draft of INRIA Lecture Notes, 1991.
• 19: Charles K. Chui , Jian-Zhong Wang, A general framework of compactly supported splines and wavelets, Journal of Approximation Theory, v.71 n.3, p.263-304, Dec. 1992 [doi>10.1016/0021-9045(92)90120-D]
• 20: R. Adams, Sobolev Spaces, Academic Press, 1975.
• 21: I.J. Scheonberg, Cardinal Spline Interpolation, CBMS-NSF Series in Applied Math #12, SIAM Publ. Philadelphia, 1973.
• 22: C.A. Hall and W. W. Meryer, Optimal error bounds for cubic spline interpolation, J. of Approx.Theory 16, 105-122 (1976).
• 23: T. R. Lucas, Error bounds for interpolating cubic splines under various end conditions, SIAM J. Numer. Anal. Vol 11, No. 3, 569-584 (1974)
• 24: C.R. De Boor, A Practical Guide to Splines, Springer-Verlag, New York, 1978.
• 25: B. K. Swartz and R.S. Varga, Error bounds for spline and L - spline interpolation, J. Approx. Theory, 6 (1972), 6-49.
• 26: H Yserentant, On the multi-level splitting of finite element spaces, Numerische Mathematik, v.49 n.4, p.379-412, Aug. 1986 [doi>10.1007/BF01389538]
• 27: S. Jaffard , Ph. Laurençot, Orthonormal wavelets, analysis of operators, and applications to numerical analysis, Wavelets: a tutorial in theory and applications, Academic Press Professional, Inc., San Diego, CA, 1993
• 28: Y. Ikebe, On the inverse of band matrix, Linear Algebra and its Applications 24, (1979) 93-97.
• 29: Wei Cai , Chi-Wang Shu, Uniform high-order spectral methods for one- and two-dimensional Euler equations, Journal of Computational Physics, v.104 n.2, p.427-443, Feb. 1993 [doi>10.1006/jcph.1993.1041]
• 30: Leland Jameson, ON THE DIFFERENTIATION MATRIX FOR DAUBECHIES-BASED WAVELETS ON AN INTERVAL, Institute for Computer Applications in Science and Engineering (ICASE), 1993
• 31: Wei Cai , JianZhong Wang, ADAPTIVE WAVELET COLLOCATION METHODS FOR INITIAL VALUE BOUNDARY PROBLEMS OF NONLINEAR PDE''S, Institute for Computer Applications in Science and Engineering (ICASE), 1993
• 32: S. Lin and E.S. Kuh, Pade Approximation Applied to Transient Simulation of Lossy Coupled Transmission Lines, in Proc. IEEE Multi-Chip Module Conf., Santa Cruz, CA, March, 1992.
• 33: K. Singhal and J. Vlach, Computation of lime domain response by numerical inversion of the Laplace transform, J. Franklin Inst., Vol. 299, no. 2, pp. 109-126, Feb., 1975.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation

General Terms:
Measurement, Theory