A fast multipole algorithm for capacitance extraction of complex 3-D geometries
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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 n3, 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 conductorsKeywords
This publication has 5 references indexed in Scilit:
- SPIDER: capacitance modelling for VLSI interconnectionsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988
- A fast algorithm for particle simulationsJournal of Computational Physics, 1987
- Rapid solution of integral equations of classical potential theoryJournal of Computational Physics, 1985
- The Electrostatic Field of Conducting Bodies in Multiple Dielectric MediaIEEE Transactions on Microwave Theory and Techniques, 1984
- Efficient Capacitance Calculations for Three-Dimensional Multiconductor SystemsIEEE Transactions on Microwave Theory and Techniques, 1973