Accuracy and efficiency of the particle mesh Ewald method

In this article, a recently proposed method called the particle mesh Ewald (PME) method for computing the long ranged Coulomb interactions in for example molecular dynamics simulations is studied. The PME method has a complexity 𝒪(N log N), where N is the total number of charges. This complexity should in particular be compared with the complexity 𝒪(N3/2) for the well known Ewald method and 𝒪(N) for the rather new (but already famous) fast multipole method (FMM). However, these complexities say nothing about which method is fastest at some finite N. The purpose of this article is thus to study the PME method and compare its efficiency with the Ewald method and the fast multipole method. To enable this, a theoretical estimate for the accuracy of the PME method as function of its truncation parameters is derived. It is shown that this estimate is very precise by comparing it with results obtained from molecular dynamics simulations of a molten NaCl. Based on this estimate and very careful time experiments, the overall necessary time overhead for the PME method as function of N and a required accuracy is predicted. By a direct comparison with a similar prediction for the Ewald method and by studying existing Ewald-FMM comparisons, it is found that the PME method is significantly faster than both the Ewald method and the fast multipole method in the important decades N≂104–105.