The Barnes–Hut Hierarchical Center-of-Charge Approximation for Fast Capacitance Extraction in Multilayered Media

The Barnes-Hut algorithm is widely used in astrophysics for solving large gravitationalN-body problems usingO(NlogN) time and memory. This reduction in computational cost is achieved by a hierarchical application of the classical center-of-mass approximation. As both gravitational and electrostatic potentials are subject to a 1/Rdependence, the Barnes-Hut algorithm is also a natural choice for rapidly evaluating interactions between charged particles. The contribution of this paper is an extension of the Barnes-Hut hierarchical clustering to the acceleration of charge interactions in stratified media. We derive and validate a closed-form expression for the shift of the center-of-charge location induced by the physical inhomogeneities and show that proper positioning of the center-of-charge ensuresO(1/R3) error decay in the field approximation. Hierarchical applications of the proposed clustering approximation is demonstrated for the construction ofO(NlogN) method-of-moment based capacitance extractors.