Comparison between O(n2) and O(n) neighbor search algorithm and its influence on superlinear speedup in parallel discrete element method (DEM) for complex-shaped particles. Issue 6 (12th October 2018)

• Record Type: Journal Article
• Authors: Yan, Beichuan; Regueiro, Richard
• Is Part Of: Engineering computations. Volume 35:Issue 6(2018)
• Page Start: 2327
• Page End: 2348
• Publication Date: 2018-10-12
• Subjects: Discrete element -- Complex-shaped particles -- Computational granularity -- Contact resolution -- Neighbor search -- Superlinear speedup; Computer-aided engineering -- Periodicals; Computer graphics -- Periodicals; 620.00285
• DOI: 10.1108/EC-01-2018-0023
• Languages: English
• ISSNs: 0264-4401

Abstract

Abstract : Purpose: This paper aims to present performance comparison between O ( n 2 ) 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 2 ) or O ( n ) neighbor search algorithm, which performs better in parallel 3D DEM computational practice? Design/methodology/approach: The O ( n 2 ) 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 2 ) 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 2 ) algorithm outperforms O ( n ) in parallel 3D DEM generally. Practical implications: Taking for granted that O ( n ) outperforms O ( n 2 ) 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 2 ) and O ( n ) neighbor search algorithms for complex-shaped 3D DEM is affected by particle shape complexity and CG. In particular, the O ( n 2 ) algorithm outperforms the O ( n ) algorithm in large-scale parallel 3D DEM simulations generally, even though this outperformance is counterintuitive.