5
$\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!

$\endgroup$
8
$\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)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! Do you know of any references that would explain this? $\endgroup$ – Andrew Aug 27 '12 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 Aug 27 '12 at 21:15
  • $\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 Aug 28 '12 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 Aug 29 '12 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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