Comparison between O(n²) and O(n) neighbor search algorithm and its influence on superlinear speedup in parallel discrete element method (DEM) for complex-shaped particles

Abstract

Purpose

This paper aims to present performance comparison between O(n²) and O(n) neighbor search algorithms, studies their effects for different particle shape complexity and computational granularity (CG) and investigates the influence on superlinear speedup of 3D discrete element method (DEM) for complex-shaped particles. In particular, it aims to answer the question: O(n²) or O(n) neighbor search algorithm, which performs better in parallel 3D DEM computational practice?

Design/methodology/approach

The O(n²) and O(n) neighbor search algorithms are carefully implemented in the code paraEllip3d, which is executed on the Department of Defense supercomputers across five orders of magnitude of simulation scale (2,500; 12,000; 150,000; 1 million and 10 million particles) to evaluate and compare the performance, using both strong and weak scaling measurements.

Findings

The more complex the particle shapes (from sphere to ellipsoid to poly-ellipsoid), the smaller the neighbor search fraction (NSF); and the lower is the CG, the smaller is the NSF. In both serial and parallel computing of complex-shaped 3D DEM, the O(n²) algorithm is inefficient at coarse CG; however, it executes faster than O(n) algorithm at fine CGs that are mostly used in computational practice to achieve the best performance. This means that O(n²) algorithm outperforms O(n) in parallel 3D DEM generally.

Practical implications

Taking for granted that O(n) outperforms O(n²) unconditionally, complex-shaped 3D DEM is a misconception commonly encountered in the computational engineering and science literature.

Originality/value

The paper clarifies that performance of O(n²) and O(n) neighbor search algorithms for complex-shaped 3D DEM is affected by particle shape complexity and CG. In particular, the O(n²) algorithm outperforms the O(n) algorithm in large-scale parallel 3D DEM simulations generally, even though this outperformance is counterintuitive.

Citation

Yan, B. and Regueiro, R. (2018), "Comparison between O(n²) and O(n) neighbor search algorithm and its influence on superlinear speedup in parallel discrete element method (DEM) for complex-shaped particles", Engineering Computations, Vol. 35 No. 6, pp. 2327-2348. https://doi.org/10.1108/EC-01-2018-0023