next up previous


2.5 Neighbourhood tables

Approximately 95 pc. of the computing time in a simulation is expended for the calculation of the pair forces, torques, energies etc. For systems of more than $N=500$ particles the interaction is usually cut off at some pair distance smaller than half the box side length: $r_{co}<L/2$. Even the scanning of all particle pairs for the condition $r_{ij}^{2}<r_{co}^{2}$ may become costly for large systems.

Verlet suggested that in such cases the possible interaction partners of each particle $i$ are listed in an array, and only the particles in that list are considered. As the molecules diffuse around, the lists must be updated regularly by an occasional $N(N-1)/2$ scan. Here is the detailed procedure:

Figure 2.4: Verlet neighbour lists: $r_{out} \approx 1.1-1.2   r_{co}$. All particles $j$ within a distance $r_{out}$ of particle $i$ are entered in a list.
\begin{figure}\includegraphics[width=210pt]{figures/verlet.ps}
\end{figure}
These lists of neighbours, $LIST(i)$, are stored in sequence, in one long array. For each $i$ a pointer $POINT(i)$ points to the start of the list of its neighbours:
Figure 2.5: Storage of Verlet lists
\begin{figure}\includegraphics[width=300pt]{figures/vlist.ps}
\end{figure}
The first setup of the lists requires $N(N-1)$ operations; every 10-20 steps the lists must be updated, again at the same cost. However, in the time of diffusion between $r_{co}$ and $r_{out}$, for each particle $i$ only the possible partners with indices $j=LIST(POINT(i))$ to $j=LIST(POINT(i+1)-1)$ need be considered.
next up previous
F. J. Vesely / University of Vienna