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.