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 gravitational N -body problems using O ( N log N ) 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/ R dependence, 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 ensures O (1/ R 3 ) error decay in the field approximation. Hierarchical applications of the proposed clustering approximation is demonstrated for the construction of O ( N log N ) method-of-moment based capacitance extractors.