|From:||"Moore, Stan" <stamoor@...3...>|
|Date:||Tue, 5 Sep 2017 19:59:58 +0000|
Here are some articles:
Comments on P3M, FMM, and the Ewald method for large periodic Coulombic systems by Pollock and Glosli, https://doi.org/10.1016/0010-4655(96)00043-4
Extension and evaluation of the multilevel summation method for fast long-range electrostatics calculations, http://dx.doi.org/10.1063/1.4883695
Comparison of scalable fast methods for long-range interactions, https://doi.org/10.1103/PhysRevE.88.063308
MSM is supposed to be better than FMM for MD because the forces are smooth, but we found P3M is often faster than MSM. If you want to use FMM with LAMMPS, you could couple LAMMPS with http://www.scafacos.de/.
From: Axel Kohlmeyer [mailto:akohlmey@...24...]
On Mon, Sep 4, 2017 at 11:21 PM, Peter Spalthoff <peter.spalthoff@...24...> wrote:
i don't consider this surprising, since the fast-multipole method has several issues, that make it in practice not as attractive for typical MD applications than many publications make you want to believe. using FMM in MD was a hot topic way back when i was a grad student, yet the deficiencies became quickly apparent, so FFT based solvers have dominated. as far as i recall, the issues with fast multipoles are the following:
- difficult to parallelize efficiently (3d-FFTs in PPPM or PME or SPME are a pain as well, but not as bad). the scaling limitations of long-range solvers for MD codes are less the algorithmic scaling of the algorithms (which usually are determined only for non-parallel calculations), but rather how well those algorithms can be parallelized efficiently across many processors in conjunction with domain decomposition. the only parallel FMM implementations that i recall existed around 20 years ago were using replicated data, which is a definite no-no for scaling across hundreds or thousands of processors (which scales *very* well for the short-range pairwise interactions).
- very large prefactor, i.e. while FMM may be linearly scaling, its advantage is diminished by the large computational effort to compute the multipole expansion hierarchies, which require lots of "expensive" math operations operations. thus the benefit of FMM is restricted to very large systems where the O(N) scaling wins over O(N log(N))
- high computational cost for high accuracy (need many levels and deep expansions)
- bad energy conservation (related to the previous point)
- unlike in cosmological simulations, where FMM is quite successful, in typical MD systems there is no benefit from "pruning", i.e. skipping over having to compute multi-pole expansions for empty spaces. this "pruning" makes FMM *very* attractive in cosmology (which you have primarily empty space). on the contracy FFT/grid based methods are costly specifically for systems with lots of empty space, as the computational cost scales with the number of grid points, not the number of atoms per volume.
not as such. LAMMPS has an equivalently scaling multi-level coulomb solver scheme in kspace style MSM, though.
however, this suffers from some of the same issues that make FMM not an overly attractive choice.
people don't tend to publish papers on failures and limitations of their pet algorithms, so there is limited chances to find any.
what most of the studies on scaling of kspace solvers omit, is to discuss is the impact of parallelization/communication. it is one thing to have asymptotic O(N) algorithmic scaling, it is a different thing to have this work in parallel across 10s or 100s of thousands of processors with only a few 100s of atoms per MPI rank.