An Investigation into Neighbouring Search Techniques in Meshfree Particle Methods: An Evaluation of the Neighbour Lists and the Direct Search

摘要

Meshfree particle methods are being increasingly employed in solving problems in automotive, aeronautics and oil industries, environmental and geophysical problems, biomechanics and medicine, hydraulic erosion, sediment transport, physics and astronomy, among other areas. Regardless of the application of the particle method, the search for neighbour particles must be done at each numerical iteration (especially in dynamic cases). In 2-D studies, the neighbour lists (linked and Verlet) are techniques commonly used in simulations. This paper presents an investigation of the computational efficiency of the linked list technique through comparison with results of simulations of the direct search (the simplest neighbour search technique). Different numbers of particles and interpolation functions have been used in the tests. By using a simple matrix in the storage of neighbour particles, an improvement in the computational efficiency (in comparison with the direct search's time processing) has not been seen when the linked list algorithm has been utilised. A similar performance between linked list and direct search has been achieved when the neighbour particles have been stored in pairs (even though the cell-linked list has been updated at each numerical iteration). From the analyses of the CPU processing times found in the problems simulated in this work, in which the efficiency of the linked list was only similar to the direct search, it was concluded that is necessary the implementation of a optimisation technique for computational time saving. The Verlet list is a linked list optimisation proposal in which the neighbour list is not update at each numerical iteration. Through an appropriate choice of the cutoff radius, it is ensured that there is no loss in accuracy in the location of neighbouring particles. Optimisation attempts using the Verlet list have been performed but the improvement in the computational efficiency are not satisfactory in all cases.