R. Everaers et K. Kremer, A FAST GRID SEARCH ALGORITHM FOR MOLECULAR-DYNAMICS SIMULATIONS WITH SHORT-RANGE INTERACTIONS, Computer physics communications, 81(1-2), 1994, pp. 19-55
We present a highly efficient grid search algorithm for performing mol
ecular dynamics simulations with short-range interactions. The method
is a variant of the link cell approach for finer grids with the follow
ing characteristics: (1) A simpler data structure with at most one par
ticle per cell, allowing an efficient and straightforward vectorizatio
n of all operations. (2) Assignment of particles to empty neighbor cel
ls to keep the density of empty cells to a minimum. 3) Sub-Cell Groupi
ng to exploit the knowledge of the exact positions of the particles re
lative to their cells. The method's tested on a Cray Y/MP 8/832 for a
Lennard-Jones fluid near its triple point. The interactions are trunca
ted at 2.5 (2(1/6) sigma. Our implementation turns out to be more than
three times faster than Rapaport's original layered link cell. If a V
erlet list is used, we are 10(40)% faster than the implementation by G
rest, Dunweg, and Kremer. The speedup due to a Verlet list is reduced
to 1.5 (2.25) and will be even lower for larger cutoffs. Thus, Grid Se
arch also offers excellent performance in cases where no Verlet list c
an be used. Applications of the algorithm to parallel computers and si
mulation methods with a variable box shape are straightforward.