Mathematical Physics - Volume II - Numerical Methods

5.6 Neighbour Search

171

It is important to observe that the methods for variation of h described above are empirical in nature. The evolution of h if treated rigorously should be coupled and consistent with the discretised form of the conservation equations. A rigorously derived Eulerian SPH with a variable smoothing length requires further research and is still outstanding. 5.6 Neighbour Search In the SPH method the interpolation points move with the continuum and as a consequence neighbours of a particle are not fixed. This implies that the SPH kernel approximation of any field variable for a particle I requires as a first step the search of the neighbouring particles j that are within the kernel support of particle I . Therefore, the neighbour search is an important and CPU time consuming step in an SPH computation. Based on the distance between the interpolation points the neighbour search routine must list the particles that are inside the neighbourhood of each particle at each time step. A direct search between every particle is particularly inefficient, requiring a time proportional to N 2 , where N is the total number of particles. A bucket sort algorithm is more efficient. In this method, an underlying grid of cells of size 2 h MAX is generated and the particles are sorted according to the box, within a background grid, in which they are located (Figure 5.2). The total extent of the grid is defined to contain all particles and is updated as the problem evolves. Then for each particle, the neighbours are searched among the particles contained in the same box and its neighbouring boxes. This allows the computational time to be cut down to a time proportional to N log N , Monaghan and Lattanzio [60].

Figure 5.2: Bucket sort and neighbour search.

Each particle I carries the information about the box that currently contains the particle. Then, to determine the neighbour list of the particle a search is performed over all particles contained in the same box and its neighbouring boxes. This results in a search over three boxes in 1 D , nine boxes in 2 D and 27 boxes in 3 D . Good algorithm design can minimise the computational cost of the search. For example the coordinates of each particle can also be stored in an integer format which reduces the