LAMMPS WWW Site - LAMMPS Documentation - LAMMPS Mailing List Archives
Re: [lammps-users] Fast Multipole Method (FMM) - does it exist and if not, why not
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [lammps-users] Fast Multipole Method (FMM) - does it exist and if not, why not

From: Axel Kohlmeyer <akohlmey@...24...>
Date: Tue, 5 Sep 2017 15:35:58 -0400

On Mon, Sep 4, 2017 at 11:21 PM, Peter Spalthoff <peter.spalthoff@...24...> wrote:
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.


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

So long and all the best from Japan,

Peter Spalthoff 

Check out the vibrant tech community on one of the world's most
engaging tech sites,!
lammps-users mailing list

Dr. Axel Kohlmeyer  akohlmey@...24...
College of Science & Technology, Temple University, Philadelphia PA, USA
International Centre for Theoretical Physics, Trieste. Italy.