Verlet list

Figure B3.3.6. The Verlet list on its construction, later, and too late. The potential cutoff range, and the list range, are indicated. The list must be reconstructed before particles originally outside the list range have penetrated tire potential cutoff sphere.

The first part of the method involves sorting all the atoms into their appropriate cells. This sorting is rapid, and may be perfonned at every step. Then, within the force routine, pointers are used to scan tlirough the contents of cells, and calculate pair forces. This approach is very efficient for large systems with short-range forces. A certain amount of unnecessary work is done because the search region is cubic, not (as for the Verlet list) spherical. 

With either method, for an energy calculation associated with an elementary move in a large system, a vast majority of the interatomic distances involving the moving parts are never computed. In contrast, Verlet lists [52] are only useful in MC calculations of dense fluids because of the local nature of elementary moves in this particular case. 

In recent years, Verlet lists have often been supplanted by (or combined with) the Linked Cell List method [7], For discussion of these techniques, see [86, 173, 303, 307], See also [49, 50, 203, 335, 341] for work on fast parallel computation of molecular forces. 

FIGURE 26.13 (a) The computational box divided into cells with size of the interaction range rcut- (h) The Verlet list of neighbors is searched in the sphere with radius shghtly larger than Tcut-... 

We then compile what are called Verlet lists which, for each element in the sample, give the list of all the elements j which are at a distance less than a certain minimum distance Vm (Figure A. 1.2), so as to be able to perform multiple steps of calculation without changing the list relative to a particle. 

If an element A is too close to the border of its environment, there is a risk that it will not be complete. In order to correct this effect, we apply the minimum-image convention, which consists of including in the Verlet list for that element A, and in the calculation (Figure A. 1.4), the elements neighboring A, situated in adjacent copies of the calculation cell, such as B. 

The smaller the value of n (the resonance order), the larger the timestep of disturbance. For example, the linear stability for Verlet is uiAt < 2 for second-order resonance, while IM has no finite limit for stability of this order. Third-order resonance is limited by /3 ( J 1.72) for Verlet compared to about double, or 2 /3 (fa 3.46), for IM. See Table 1 for limiting values of wAt corresponding to interesting combinations of a and n. This table also lists timestep restrictions relevant to biomolecular dynamics, assuming the fastest motion has period of around 10 fs (appropriate for an O-H stretch, for example). 

Pointer and neighbour arrays can be used to implement the Verlet neighbour list. 

The basic methods to treat short-range interactions are often called by the common implementation methods used, i.e. Verlet neighbor lists [92] and linked lists [93,94]. We believe that this nomenclature should be reserved for the respective implementation methods since they tend to stand in the way for better implementation methods that could be developed. It is more appropriate to use names which describe the actual algorithmic ideas. In support of this view is the observation that neither Verlet neighbor lists nor linked list can be very efficient on cache-based processors, since they have a tendency to access memory in an unstructured way. The same access pattern is also a headache on vector architectures. Examples of data structures that are both efficient and likely to get better cache reuse can be found in [70,71,95]. An improvement in the construction of neighbor lists can be found in [96]. It is notable that Everaers and Kremer [71] also report very good vectorization of the method that have developed. 

If the Verlet method is used, then it turns out that the insertion of (3.18) into (3.19) results in a quartic polynomial that must be solved for each particle pair. Care must be taken in solving these quartics to ensure that roots are not missed. Using hash tables, neighbor lists and similar methods (like those used to compute non-bonded forces), the number of computations can be greatly reduced. Importantly, the calculations needed are all explicit and finite (no iteration is needed). 

The cutoff radius approach reduces the computation time significantly since the potential/ force calculations are skipped for those atoms that are not in the cutoff sphere. However, the separations of all distinct pairs stiU have to be calculated at each time step to examine if they are in the interaction range or not, which also takes a lot of time. The situatimi gets worse rapidly for larger systems since this calculation scales with N. In order to solve this problem, Verlet introduced a technique in 1967 [4] and the strategy is to construct a neighbor list for each atom, which... 

In practise, Brode-Ahlrichs decomposition is usually combined with a Verlet neighbour list for each atom. One nice feature of this is that it is only necessary for each node to hold the neighbourlist for the atoms it is responsible for. This means that the full neighbourlist, which can taJce up large amounts of memory, can be distributed over each processor in the system, with each one storing only a partial neighbourlist. 

Because we are interested in systems with rather short-range interactions with a well-defined cut-off, it is inefficient to examine all of the pairs of particles ij at each time-step to determine which ones have a nonzero force between them. An alternative is to divide the simulation cell into smaller cells of size r< -t- r, where is a small skin of order 0.3-0.5ct. Now one simply has to check pairs within neighboring cells to determine which pairs ij have a nonzero force. The extra skin allows one to create a list of neighbors, which only has to be updated every 10-20 time steps. Combining the link cell with a Verlet neighbor table is the most efficient method for doing any off-lattice simulation with short-range interactions. To obtain... 

Fig. 10. Calculated free energy barrier for homogeneous crystal nucleation of hard-sphere colloids. The results are shown for three values of the volume fraction. The drawn curves are fits to the CNT-expression Eq. (1). For the identification of solid like particles we used the techniques described before. The cutoff for the local environment was set to Vq = 1.4

---