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 189p(4) 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 40p(2) + 6p(3) operations per box. (C) 2002 Elsevier Science (USA).