FAST CAPACITANCE EXTRACTION OF GENERAL 3-DIMENSIONAL STRUCTURES

In [1], a boundary-element based algorithm is presented for computing the capacitance of three-dimensional m-conductor structures whose computational complexity grows nearly as mn, where n is the number of elements used to discretize the conductor surfaces. In that algorithm, a generalized conjugate residual iterative technique is used to solve the n x n linear system arising from the discretization, and a multipole algorithm is used to compute the iterates. In this paper, several improvements to that algorithm are described which make the approach in [1] applicable and computationally efficient for almost any geometry of conductors in a homogeneous dielectric. In particular, a new adaptive multipole algorithm is described, along with a strategy for accelerating the iterative algorithm by exploiting electrostatic screening. Results using these techniques in a program which computes the capacitance of general three-dimensional structures are presented to demonstrate that the new algorithm is nearly as accurate as the more standard direct factorization approach, and is more than two orders of magnitude faster for large examples.