A precorrected-FFT approach for capacitance extraction of general three-dimensional structures

In the design of high performance integrated circuits and integrated circuit packaging, there are many cases where the self and coupling capacitances are important for determining final circuit speeds or functionality. The traditional boundary-element technique and Gaussian elimination for solving the integral equation associated with the capacitance extraction problem require O(N/sup 3/) operations and O(N/sup 2/) memory storage. These approaches become computationally intractable when a large number of elements are used, thus limiting the size of the problem that can be analyzed. In this paper, a generalized conjugate residual iterative technique is used to solve the linear system arising from the discretization, and a precorrected-FFT method is then employed to accelerate the matrix-vector products in the iterates. This technique requires O(NlogN) operations and O(N) memory storage to perform a potential calculation.