A fast wavelet collocation method for high-speed VLSI circuit simulation
Authors: 
D. Zhou, N. Chen, W. CaiAuthors Info & Claims
Pages 115 - 122
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]
L.O. Chua and P. M. Lin, Compuler-Aided Analysis of Eleclronic Circuils: Algorilhms, and Compulalional Techniques, Englewood Cliffs, NJ: Prentice-Hall, 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]
S. Jaffard, Wavelet methods for fast resolution of elliplic problems, SIAM Journal on Numerical Analysis, 29(4):965-986, 1992.
[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]
C.K. Chui, An Introduction to Wavelets, Academic Press, 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]
C.K.Chui and J.Z. Wang, A general framework of compactly supported splines and wavelets, J. Approx. Theory, 71(1992) 263-304.
[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]
n. Yserentant, On the multi-level splitting of finile elmenl spaces. Numer. Math. 49, 379-412 (19s6).
[27]
S. Jaffard, Ph. Laurencot, Orlhogonal wavelets, analysis of operators, and applications to numerical analysis, in "Wavelets- A Tutorial in Theory and Applications." C.K. Chui (ed). Acad. Press, 542-601 (1992).
[28]
Y. Ikebe, On the inverse of band matrix, Linear Algebra and its Applications 24, (1979) 93-97.
[29]
W. Cai and C.W. Shu, uniform form high order spectral methods for one and two dimensional euler equations, a. Compt. Phys. 104 (1993), 427-443.
[30]
L. Jameson, On the differential matrix for Daubechies-based wavelets on an Interval, ICASE Report 93-94, December, 1993.
[31]
W. Cai and J.Z. Wang, Adaptive Multi-resolution Coolocalion Methods for Initial Boundary Value Problems of Nonlinear PDEs, ICASE Report 93- 48, to appear in SIAM Numerical analysis (1995).
[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
- A fast wavelet collocation method for high-speed VLSI circuit simulation
Recommendations
Haar wavelet collocation method for three-dimensional elliptic partial differential equations
A new collocation method based on Haar wavelet is presented for numerical solution of three-dimensional elliptic partial differential equations with Dirichlet boundary conditions. An important advantage of the method is that it can be applied to both ...
A Chebyshev spectral collocation method for solving Burgers'-type equations
In this paper, we elaborated a spectral collocation method based on differentiated Chebyshev polynomials to obtain numerical solutions for some different kinds of nonlinear partial differential equations. The problem is reduced to a system of ordinary ...
Numerical solution of high-order VolterraFredholm integro-differential equations by using Legendre collocation method
The main purpose of this paper is to use the Legendre collocation spectral method for solving the high-order linear VolterraFredholm integro-differential equations under the mixed conditions. Avoiding integration of both sides of the equation, we ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright (c) 1995 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
Sponsors
- SIGDA: ACM Special Interest Group on Design Automation
- IEEE-CS: Computer Society
Publisher
IEEE Computer Society
United States
Publication History
Published: 01 December 1995
Check for updates
Qualifiers
- Article
Conference
ICCAD '95
Sponsor:
- SIGDA
- IEEE-CS
ICCAD '95: International Conference on Computer Aided Design
November 5 - 9, 1995
California, San Jose, USA
Acceptance Rates
Overall Acceptance Rate 457 of 1,762 submissions, 26%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 264Total Downloads
- Downloads (Last 12 months)56
- Downloads (Last 6 weeks)18
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in