Verlet neighbor 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... 

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

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

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. 

---