Sparse transformations and preconditioners for 3-D capacitance extraction
Authors:
- V. SarinVSV. Sarin
- Weiping ShiWSWeiping Shi
- 29 August 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 24 (9) , 1420-1426
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/spl times/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/spl times/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/spl times/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.Keywords
This publication has 11 references indexed in Scilit:
- Electromagnetic parasitic extraction via a multipole method with hierarchical refinement2003
- A multiscale method for fast capacitance extraction2003
- Iterative Methods for Sparse Linear Systems2003
- A fast hierarchical algorithm for three-dimensional capacitance extractionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002
- Large-scale capacitance calculation2000
- A precorrected-FFT method for electrostatic analysis of complicated 3-D structuresIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1997
- IES/sup 3/: a fast integral equation solver for efficient 3-dimensional extraction1997
- Multipole-accelerated capacitance extraction algorithms for 3-D structures with multiple dielectricsIEEE Transactions on Circuits and Systems I: Regular Papers, 1992
- FastCap: a multipole accelerated 3-D capacitance extraction programIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- The Electrostatic Field of Conducting Bodies in Multiple Dielectric MediaIEEE Transactions on Microwave Theory and Techniques, 1984