Dear all,
I have used LAMMPS in the past for MD simulations and became interested in
long range solving methods.
I will (hopefully) join a lab working on fast multipole methods and in
that context was wondering if they are employed in LAMMPS.
I scoured the archives and to my surprise found nothing on the subject but
a single vague claim that LAMMPS does not contain FMM code.
​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.
My questions are thus:
Does LAMMPS contain FMM code?
​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.
If not, why is that the case?
If someone could point me to some literature on the subject, that would
also be of great help.
​people don't tend to publish papers on failures and limitations of their
pet algorithms, so there is limited chances​ to find any.
The following is just some (hopefully correct) information I have gathered
in the research process:
The LAMMPS documentation on long range solvers mainly talks about Ewald
and related pppm methods. Depending on the implementation, these methods
are O(N Log N) (Wikipedia on Ewald summation) or even O(N) (a paper I
found), but FMM codes can achieve the same asymptotic characteristics. I
don't know anything about the hidden constants and am not sure how the code
in LAMMPS scales (I sadly cannot try myself at the moment), but it would
seem that FMMs might be competitive.
I have found papers describing the use of FMM with periodic boundary
conditions.
​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.
axel.