Virtual 3-D Multipole accelerated extractor for VLSI parasitic interconnect capacitance

With development of the VLSI circuits towards the deep submicron,it is in great need of calculating the parasitic capacitance quickly and precisely to gain correct design of circuits with high performance. A virtual 3-D extractor of the single dielectric is presented in this paper. In the indirect boundary integral equations based on the potential theory, the plane charge distribution on the surface of conductors is replaced with mesh charge distribution to reduce the complexity of 3-D structure, and we use the multipole-accelerated algorithm to further depress the computational complexity. Since it reserves the geometry of three-dimensional structure and reduces the integral of electrical charge from two-dimensions to one-dimension, it obtains not only enough accuracy but also a high computational speed. Numerical results show that its computational complexity is about O (n), where n is the number of the discrete variables.