A fast hierarchical algorithm for 3D capacitance extraction
Conference Paper

 Overview

 Identity

 Additional Document Info

 View All

Overview
abstract

© 1998 ACM. We present a new algorithm for computing the capacitance of threedimensional perfect electrical conductors of complex structures. The new algorithm is significantly faster and uses much less memory than previous best algorithms, and is kernel independent. The new algorithm is based on a hierarchical algorithm for the nbody problem, and is an acceleration of the boundary element method for solving the integral equation associated with the capacitance extraction problem. The algorithm first adaptively subdivides the conductor surfaces into panels according to an estimation of the potential coefficients and a usersupplied error bound. The algorithm stores the potential coefficient matrix in a hierarchical data structure of size O(n), although the matrix is size n 2 if expanded explicitly, where n is the number of panels. The hierarchical data structure allows us to multiply the coefficient matrix with any vector in O(n) time. Finally, we use a generalized minimal residual algorithm to solve m linear systems each of size n×n in O(mn) time, where m is the number of conductors. The new algorithm is implemented and the performance is compared with previous best algorithms. For the k×k bus example, our algorithm is 100 to 40 times faster than FastCap, and uses 1/100 to 1/60 of the memory used by FastCap. The results computed by the new algorithm are within 2.7% from that computed by FastCap.
author list (cited authors)

Shi, W., Liu, J., Kakani, N., & Yu, T.
publication date
published in
Identity
International Standard Book Number (ISBN) 10
Additional Document Info