What is the scaling or order of molecular dynamics (MD) simulations?

Question

Often in computational science, we talk about the scaling or order of a particular method ($\mathcal{O}(N)$, $\mathcal{O}(N^2)$, $\mathcal{O}(N \log N)$, etc.).

I am having a really difficult time finding a resource (book, journal article, or website) that gives an order $\mathcal{O}$ (with respect to $N$, the number of particles) for molecular dynamics (MD) simulations. Can you please help me? Thank you!

score 10 · Accepted Answer · answered Aug 27 '12 at 20:24

10

Since the size of each type of atom is fixed, for a given level of accuracy the asymptotic cost is dominated by far field electrostatic interactions. These are $O(n)$ using multigrid and $O(n \log n)$ using FFTs. Thus the optimal complexity is $O(n)$ per time step as a function of the number of atoms simulated. The time step is also asymptotically constant, so the total complexity of simulating $n$ particles for time $t$ is $O(nt)$.

answered Aug 27 '12 at 20:24

Geoffrey Irving

3,969
18
41

Thank you! Do you know of any references that would explain this? – Andrew Aug 27 '12 at 20:51
1

The first few of these might help: http://www.deshawresearch.com/publications.html. In particular the first Ewald paper. – Geoffrey Irving Aug 27 '12 at 21:15
1

But the factor hidden in the $O$ can be huge, as it contains a factor for the number of local interactions that must be computed for each molecule. – Arnold Neumaier Aug 28 '12 at 07:32
Yes, the constant factor is $O(L^3/R^3)$, where $L$ is the length scale of near field electrostatics and $R$ is the radius of atoms. – Geoffrey Irving Aug 29 '12 at 00:29

What is the scaling or order of molecular dynamics (MD) simulations?

1 Answers1