When a large number of separate objects interact, N*(N-1)/2 interactions can occur. At any instant a given object may interact strongly with only a few of the N-1 others. Unfortunately, keeping lists of the other objects with which it interacts or recomputing these nearest neighbors each timestep is computationally expensive. These 'nearest neighbors' problem has persisted in computational Physics and computational geometry for several decades. We need efficient algorithms which select important nearest-neighbor interactions without having to check and analyze N2 interactions. To date the best algorithms which scale as N, rather than N2, are scalar algorithms which address memory randomly. This report introduces an efficient 3D nearest-neighbor algorithm whose cost scales as N and which vectorizes easily using data from contiguous memory locations. A Monotonic Logical Grid (MLG) for storing the object data is defined dynamically so that objects which are adjacent in real space automatically have close address indices in the compact MLG data arrays. The data values for each object are stored at a location (i,j,k) in the MLG such that the X positions of all objects increase monotonically with index i, the Y positions increase monotonically with index j, and the Z positions increase monotonically with index k. SUch a well-structured mapping from the real positions to regular, compact data arrays can always be found. Further, when object motions result in a local violation of spatial monotonicity, another MLG always can be found nearby. This means that local changes in the object positions and hence spatial ordering do not trigger global changes in where these object data are stored in the MLG.
展开▼
