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 logN) 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 ³) error decay in the field approximation. Hierarchical applications of the proposed clustering approximation is demonstrated for the construction of O(N logN) method-of-moment based capacitance extractors.