IES3: a fast integral equation solver for efficient 3-dimensional extraction

ABSTRACT

Integral equation techniques are often used to extract models of integrated circuit structures. This extraction involves solving a dense system of linear equations, and using direct solution methods is prohibitive for large problems. In this paper, we present IES/sup 3/ (pronounced "ice cube"), a fast Integral Equation Solver for three-dimensional problems with arbitrary kernels. Extraction methods based on IES/sup 3/ are substantially more efficient than existing multipole-based approaches.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: L. Greengard and V. Rohklin. A new version of the fast multipole method for the Laplace equation in three dimensions. Technical Report YALEU/DCS,/RR-1115, Yale University Department of Computer Science, September 1996.
• 3: 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]
• 4: Roger F. Harrington, Field Computation by Moment Methods, Wiley-IEEE Press, 1993
• 5: M. Kamon, M. J. Tsuk, and J.White. FAS- THENRY: A multipole-accelerated 3-d inductance extraction program. IEEE Transactions on Microwave Theory and Techniques, 42(9):1750- 1758, September 1994.
• 6: 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]
• 7: K. Nabors and J. White. Fastcap: A multipoleaccelerated 3-d capacitance extraction program. IEEE Transactions on Computer-Aided Design, 10(10):1447-1459, November 1991.
• 8: K. Nabors and J. White. Multipole-accelerated capacitance extraction for 3-d structures with multiple dielectrics. IEEE Transactions on Circults and Systems, 39(11):946-954, November 1992.
• 9: 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
• 10: S. M. Rao, T. K. Sarkar, and R. F. Harrington. The electrostatic field of conducting bodies in multiple dielectric media. IEEE Transactions on Microwave Theory and Techniques, 32(11):1441- 1448, November 1984.
• 11: 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]
• 12: J. Stoer and R. Bulirsch. Introduction to Numerical Analysis. Springer-Verlag, New York, 1979.
• 13: W. T. Weeks. Calculation of coefficients of capacitance of multiconductor transmission lines in the presence of a dielectric interface. IEEE Transactions on Microwave Theory and Techniques, 18(1):35-43, January 1970.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Advanced technologies

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  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.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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

Keywords:
3-dimensional extraction, IES/sup 3/, arbitrary kernels, circuit CAD, integral equation solver, integrated circuit structures