Singularity-treated quadrature-evaluated method of moments solver for 3-D capacitance extraction

ABSTRACT

While research work on fast integral equation solver has resulted in several algorithms of similar linear equation solving performance, it has been well observed that the convergence of capacitance versus discretization is rather slow due to the most commonly used first-order collocation or Galerkin methods. This paper reports a new high-order scheme, Quadrature-evaluated Method of Moments Solver (QMMS), that uses high-order weighting and Gaussian quadrature to optimally handle the singularities at the edges and corners. For practical interconnect extraction problems, singularities at edges are analytically known and the corresponding Gaussian nodes allocation affords a near optimal discretization scheme. The new formulation avoids the special position-dependent quadrature rules, and surprisingly, provides a well-behaved matrix that converges rapidly without any pre-conditioning. Combining the high-order scheme with a kernel-independent fast solver yields an efficient algorithm for 3-D capacitance extraction.

REFERENCES

• 1: Roger F. Harrington, Field Computation by Moment Methods, Krieger Publishing Co., Inc., Melbourne, FL, 1982
• 2: J.D. Jackson. Classical electrodynamics. Wiley, New York, 3rd ed. edition, 1999.
• 3: 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
• 4: Sharad Kapur , David E. Long, High-order Nyström schemes for efficient 3-D capacitance extraction, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.178-185, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288604]
• 5: W.Sun, W. Wei-Ming Dai, and W. Hong. Fast parameter extraction of general interconnects using geometry independent measured equation of invariance. IEEE Transactions on Microwave Theory and Techniques, 45(5):827-36, May 1997.
• 6: Johannes Tausch , Jacob White, A multiscale method for fast capacitance extraction, Proceedings of the 36th ACM/IEEE conference on Design automation, p.537-542, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309994]
• 7: Jinsong Zhao , Wayne W. M. Dai , Sharad Kapur , David E. Long, Efficient thee-dimensional extraction based on static and full-wave layered Green's functions, Proceedings of the 35th annual conference on Design automation, p.224-229, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277103]

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Gaussian quadrature
  G.2 DISCRETE MATHEMATICS

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