Sparse transformations and preconditioners for 3-D capacitance extraction Academic Article uri icon


  • Three-dimensional (3-D) capacitance-extraction algorithms are important due to their high accuracy. However, the current 3-D algorithms are slow and thus their application is limited. In this paper, we present a novel method to significantly speed up capacitance-extraction algorithms based on boundary element methods (BEMs), under uniform and multiple dielectrics. The n n coefficient matrix in the BEM is dense, even when approximated with the fast multipole method or hierarchical-refinement method, where n is the number of panels needed to discretize the conductor surfaces and dielectric interfaces. As a result, effective preconditioners are hard to obtain and iterative solvers converge slowly. In this paper, we introduce a linear transformation to convert the n n dense coefficient matrix into a sparse matrix with O(n) nonzero entries, and then use incomplete factorization to produce a very effective preconditioner. For the k k bus-crossing benchmark, our method requires at most four iterations, whereas previous best methods such as FastCap and HiCap require 10-20 iterations. As a result, our algorithm is up to 70 times faster than FastCap and up to 2 times faster than HiCap on these benchmarks. Additional experiments illustrate that our method consistently outperforms previous best methods by a large magnitude on complex industrial problems with multiple dielectrics. 2005 IEEE.

published proceedings


author list (cited authors)

  • Yan, S., Sarin, V., & Shi, W. P.

citation count

  • 15

complete list of authors

  • Yan, S||Sarin, V||Shi, WP

publication date

  • September 2005