Fast algorithms for particle searching and positioning by cell registration and area comparison - Ogami, Yoshifumi (Trends in Computer Science and Information Technology, 2021)
In the direct simulation Monte Carlo method and multi-phase flow calculations, structured and unstructured grid systems for complex geometries necessitate the time-consuming process of searching a large number of cells to position target particles. This paper proposes effective computational methods for particle searching and positioning that are applicable to structured and unstructured grid systems. Firstly, two methods are introduced to limit the cells to search: the surrounding cell registration method and the Cartesian cell registration method. In the case of two-dimensional potential flow around a circular cylinder, as an application of the proposed methods, it is demonstrated that the surrounding cell registration method is 232 times faster than the method of searching all the cells until the cells occupied by the target particles are found, whereas the Cartesian cell registration method is 200 times faster with the appropriate parameters. Secondly, a method called the area comparison method is introduced to position a target particle and find the exit edge of the cell at which a trajectory of the particle exits. It is demonstrated that the area comparison method can position particles 1.15–1.2 times faster than particle-to-the-left positioning because the latter is implemented with multiple if-statements, while the former has only one.