What is the computational complexity of calculating the force due to pair potential in a system of N atoms?

LAMMPS LAMMPS General Discussion
1

Hello everyone,

I am currently investigating the different algorithms used in N-body problems to reduce the computational complexity. As far as I understand, LAMMPS uses a direct force calculation approach by calculating the force on all pairs of atoms, which has a complexity of N^2, but excludes all the interactions beyond a cutoff distance d, which reduces the complexity to a smaller value depending on the choice of the cutoff distance. So, my question is: Does LAMMPS use any other approximation to further reduce the computational complexity, or does it follow the approach described above ?

Best regards,
Rafid

2

https://docs.lammps.org/Developer_parallel.html

3

Thank you so much for your answer. My question wasn’t clear, I apologize. I will try to restate it:

The algorithms that I am considering are approximation algorithms such as Barnes-Hut (BH) and the Fast Mulptipole Method (FMA). I do know that LAMMPS doesn’t use these 2 algorithms based on an answer that I found in another thread in this forum. However, what I want to ask is, regardless of parallelization, does LAMMPS use any approximation algorithm ?

Thank you.

4

That must be an old message.

What you are asking about is not really what I would call an “approximation algorithm” but rather a long-range interaction solver. LAMMPS directly supports Ewald summation, PPPM, and multi-level summation (MSM). The MSM is in many ways similar to the fast multipole method if not superior. These can be applied to Coulomb interactions and Ewald and PPPM also to the r^6 dispersion term of Lennard-Jones interactions. Fast Multipole and MSM are quite “expensive” to compute when you desire good accuracy which is why most people end up using PPPM (which is equivalent to the also very popular Particle-Mesh Ewald solvers).

Through the SCAFACOS package LAMMPS also interfaces to the ScaFaCoS library which provides a few more solvers including a fast multipole solver.
https://docs.lammps.org/kspace_style.html

1 Like
5

Any direct pair-wise calculation in LAMMPS is O(N), not O(N^2), since it uses a fixed cutoff distance, though the prefactor could be large if using a large cutoff. Ewald sum is O(N^3/2) best case with optimal parameters, otherwise it is O(N^2). PPPM is O(N*logN), MSM is O(N) but normally has a larger prefactor compared to PPPM. Other methods such as FMM which is O(N) are available in SCAFACOS package as Axel mentioned.

1 Like
6

Thank you for all your answers. It’s very helpful.