A fast multipole algorithm for capacitance extraction of complex 3-D geometries

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 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 that the computation grows like n³, where n is the number of tiles needed to accuracy-discretize the conductor surface charges. The authors 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