Fast Multipole Method (FMM) - does it exist and if not, why not

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.

My questions are thus:
Does LAMMPS contain FMM code?
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.

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.

I am happy to provide some sources when I am back on my computer.

So long and all the best from Japan,

Peter Spalthoff

1 Like

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.

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/.

Stan