A floating random-walk algorithm for extracting electrical capacitance

In 1991, we developed a floating random-walk algorithm to extract electrica l capacitance in 2D structures. Since then, our work has evolved into a pow erful commercial 3D CAD tool, QuickCap(TM), capable of finding capacitance in integrated circuits (ICs) represented by multi-gigabyte databases. The a lgorithm has proven to be exceptionally powerful and is now finding accepta nce in an application area traditionally dominated by deterministic algorit hms. We present the theory underlying the floating random-walk algorithm: a formulation of capacitance as an integral of infinite dimensionality evalu ated by Monte Cal lo integration. A single Monte Carlo sample of the integr al corresponds to a floating random-walk. We also discuss performance chara cteristics of QuickCap and we summarize our contributions in other applicat ion areas. (C) 2001 IMACS. Published by Elsevier Science B.V. All rights re served.