Sparse Transformations and Preconditioners for 3-D Capacitance Extraction Academic Article uri icon

abstract

  • 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.

author list (cited authors)

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

publication date

  • January 1, 2005 11:11 AM