A fast hierarchical algorithm for 3-D capacitance extraction

ABSTRACT

We presen t a new algorithm for computing the capacitance of three-dimensional perfect electrical conductors of complex structures. The new algorithm is significantly faster and uses muc h less memory than previous best algorithms, and is kernel independent. The new algorithm is based on a hierarchical algorithm for the n-body problem, and is an acceleration of the boundary-element method for solving the integral equation associated with the capacitance extraction problem. The algorithm first adaptively subdivides the conductor surfaces into panels according to an estimation of the potential coefficients and a user-supplied error band. The algorithm stores the poten tial coefficient matrix in a hierarchical data structure of size O(n), although the matrix is size n2 if expanded explicitly, wheren is the n umber of panels. The hierarchical data structure allows us to multiply the coefficient matrix with an y vector in O(n) time. Finally, w e use a generalized minimal residual algorithm to solve m linear systems each of size n × n in O(mn) time, where m is the n umber of conductors. The new algorithm is implemented and the performance is compared with previous best algorithms. F or the k × k bus example, our algorithm is 100 to 40 times faster than F astCap, and uses 1/100 to 1/60 of the memory used by F astCap. The results computed by the new algorithm are within 2.7% from that computed by FastCap.

REFERENCES

• 1: A. A. Appel, "An efficient program for many-body simulation,'' SIAM j. Scientific and Statistical Computing, Vol. 6, No. 1, 1985, 85-103.
• 2: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 3: Klaas Esselink, The order of Appel's algorithm, Information Processing Letters, v.41 n.3, p.141-147, March 6, 1992 [doi>10.1016/0020-0190(92)90043-U]
• 4: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 5: L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
• 6: L. Greengard, The Rapid Evaluation of Potential Fields in Particle Systems, MIT Press, Cambridge, Massachusetts, 1988.
• 7: Pat Hanrahan , David Salzman , Larry Aupperle, A rapid hierarchical radiosity algorithm, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.197-206, July 1991
• 8: Sharad Kapur , David E. Long, IES3: a fast integral equation solver for efficient 3-dimensional extraction, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.448-455, November 09-13, 1997, San Jose, California, United States
• 9: Sharad Kapur , Jinsong Zhao, A fast method of moments solver for efficient parameter extraction of MCMs, Proceedings of the 34th annual conference on Design automation, p.141-146, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266051]
• 10: K. Nabors and J. White, "FastCap: A multipole accelerated 3-D capacitance extraction program," IEEE Trans. CAD, Vol. 10, No. 11, Nov. 1991, 1447-1459.
• 11: K. Nabors , J. White, Multipole-accelerated 3-D capacitance extraction algorithms for structures with conformal dielectrics, Proceedings of the 29th ACM/IEEE conference on Design automation, p.710-715, June 08-12, 1992, Anaheim, California, United States
• 12: K. Nabors , F. T. Korsmeyer , F. T. Leighton , J. White, Preconditioned, adaptive, multipole-accelerated iterative methods for three-dimensional first-kind integral equations of potential theory, SIAM Journal on Scientific Computing, v.15 n.3, p.713-735, May 1994 [doi>10.1137/0915046]
• 13: J. R. Phillips , J. White, A precorrected-FFT method for capacitance extraction of complicated 3-D structures, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.268-271, November 06-10, 1994, San Jose, California, United States
• 14: Youcef Saad , Martin H Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.856-869, July 1986 [doi>10.1137/0907058]
• 15: Weikai Sun , Wayne Wei-Ming Dai , Wei Hong, Fast parameters extraction of general three-dimension interconnects using geometry independent measured equation of invariance, Proceedings of the 33rd annual conference on Design automation, p.371-376, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240589]
• 16: D. R. Wilton, et al., "Potential integration for uniform and linear source distributions on polygonal and polyhedral domains," IEEE Trans. Antennas and Propagation, Vol. AP-32, No. 3, March 1984, 276-281.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
emulation, functional simulation, reconstruction, visibility