Domain decomposition and non-uniform spherical grid interpolation (NSGI) algorithm for fast solution of potential problems

A novel scheme facilitating numerically efficient evaluation of the potential produced by a given charge distribution is presented. The algorithm is based on the observation that locally the the potential produced by a finite size source is an essentially bandlimited function of the angles and a polynomial in the reciprocal radial distance. Therefore the potential can be interpolated from its samples at a small number of points of a nonuniform spherical grid. With this in mind, the problem geometry is decomposed into hierarchy of subdomains. Potential computation is performed separately for charges residing in each subdomain on the finest level. The proposed multilevel algorithm comprises interpolation and aggregation of potentials for each group of subdomains to compute the potential of a larger parent subdomain. The resulting hierarchical algorithm attains an asymptotic complexity of O(N).