7
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
10
$\begingroup$

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)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you! Do you know of any references that would explain this? $\endgroup$
    – Andrew
    Commented Aug 27, 2012 at 20:51
  • 1
    $\begingroup$ The first few of these might help: deshawresearch.com/publications.html. In particular the first Ewald paper. $\endgroup$
    – Geoffrey Irving
    Commented Aug 27, 2012 at 21:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – Arnold Neumaier
    Commented Aug 28, 2012 at 7:32
  • $\begingroup$ 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. $\endgroup$
    – Geoffrey Irving
    Commented Aug 29, 2012 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.