A fast pairlist-construction algorithm for molecular simulations under periodic boundary conditions

A new grid-cell algorithm is presented that permits the fast construction of cutoff-based nonbonded pairlists in molecular simulations under periodic boundary conditions based on an arbitrary box shape. The key features of the method are (1) the use of a one-dimensional mask array (to determine which grid cells contain interacting atoms) that incorporates the effect of periodicity, and (2) the grouping of adjacent interacting cells of the mask array into stripes, which permits the handling of empty cells with a very low computational overhead. Testing of the algorithm on water systems of different sizes (containing about 2000 to 11,000 molecules) shows that the method (1) is about an order of magnitude more efficient compared to a standard (double-loop) algorithm, (2) achieves quasi-linear scaling in the number of atoms, (3) is weakly sensitive in terms of efficiency to the chosen number of grid cells, and (4) can be easily parallelized. (C) 2004 Wiley Periodicals, Inc.