A floating random-walk algorithm for extracting electrical capacitance

In 1991, we developed a floating random-walk algorithm to extract electrical capacitance in 2D structures. Since then, our work has evolved into a powerful commercial 3D CAD tool, QuickCap™, capable of finding capacitance in integrated circuits (ICs) represented by multi-gigabyte databases. The algorithm has proven to be exceptionally powerful and is now finding acceptance in an application area traditionally dominated by deterministic algorithms. We present the theory underlying the floating random-walk algorithm: a formulation of capacitance as an integral of infinite dimensionality evaluated by Monte Carlo integration. A single Monte Carlo sample of the integral corresponds to a floating random-walk. We also discuss performance characteristics of QuickCap and we summarize our contributions in other application areas.