Accelerated Cartesian expansions -: A fast method for computing of potentials of the form R-v for all real v

The need to compute potentials of the form R-nu for nu >= 1 occur in a variety of areas ranging from electromagnetics to biophysics to molecular dynamics to astrophysics, etc. For instance, Coulomb, London, Lennard-Jones, H-bonds are of the form nu = 1, 5, 6 (and 12), 10, respectively. For a systems with N source/observation points, the cost of computing these potentials scales proportional to O(N-2). Methods to overcome this computational bottleneck have been a popular research topic for quite some time. For instance, the fast multipole method (FMM) and their cousins-tree codes-have revolutionized the computation of electrostatic potentials (nu = 1). These methods rely on a hierarchical decomposition of the computational domain, i.e, construction of a regular oct-tree decomposition, and exploits the principle of divide and conquer to compute potentials at each observation point. This paper presents two methods, in the vein of FMM, albeit based on Cartesian tensors. The salient features of the first are as follows: (i) it relies on totally symmetric tensors and (ii) the errors are independent of the height of the tree. The second method is presented specifically for nu = 1, and relies on traceless totally symmetric Cartesian tensors. Using the relationship between traceless Cartesian tensors and spherical harmonics, it will be shown that this technique has the same computational cost as the classical FMM. Generalization of the second method for nu not equal 1 is trivial; however, one needs to use totally symmetric tensors instead. Finally, in the whole computation scheme, only the translation operator (that used to traverse across the tree) depends on v. Convergence of the proposed method is proven for all v E R. Numerical results that validate the cost and accuracy are presented for several potential functions; these include those typically encountered in the analysis of physical systems (Coulombic, Lennard-Jones, Lattice gas). (C) 2007 Elsevier Inc. All rights reserved.