A New Version of the Fast Multipole Method for Screened Coulomb Interactions in Three Dimensions

We present a new version of the fast multipole method (FMM) for screened Coulomb interactions in three dimensions. Existing schemes can compute such interactions in O(N) time, where N denotes the number of particles. The constant implicit in the O(N) notation, however, is dominated by the expense of translating far-field spherical harmonic expansions to local ones. For each box in the FMM data structure, this requires 189p4 operations per box, where p is the order of the expansions used. The new formulation relies on an expansion in evanescent plane waves, with which the amount of work can be reduced to 40p2+6p3 operations per box.