Fast Multipole Algorithm for Capacitance Extraction of Complex 3-D (Three Dimensional) Geometries

摘要

In this paper a fast algorithm for computing the capacitance of a complicated 3-D geometry of ideal conductors in a uniform dielectric is described. The method is an acceleration of the standard integral equation approach for multiconductor capacitance extraction. These integral equation methods are slow because they lead to dense matrix problems which are typically solved with some form of Gaussian elimination. This implies the computation grows like cu m , where cu m is the number of tiles needed to accurately discretize the conductor surface charges. In this paper we present a preconditioned conjugate-gradient iterative algorithm with a multipole approximation to compute the iterates. This reduces the complexity so that accurate multiconductor capacitance calculations grow as nm where m is the number of conductors. (RH)