Title: Efficiency of particle search methods in smoothed particle hydrodynamics: a comparative study (part I)

Authors: E. Plaza; Leonardo Di G. Sigalotti; Luis Pérez; Jorge Troconis; Wilfredo Angulo; María Castro

Addresses: Departamento de Física, Laboratorio de Fluidos, Escuela Superior Politécnica del Litoral (ESPOL), ESPOL Polytechnic University, 30.5 km, Vía Perimetral Guayaquil, 09-01-5863, Ecuador; Laboratorio de Física de Fluidos y Plasmas, Instituto Venezolano de Investigaciones Científicas (IVIC), Altos de Pipe, 21827, Venezuela ' Departamento de Ciencias Básicas, Universidad Autónoma Metropolitana-Azcapotzalco (UAM-A), Av. San Pablo 180, 02200, Ciudad de México, Mexico ' Laboratorio de Física de Fluidos y Plasmas, Instituto Venezolano de Investigaciones Científicas (IVIC), Altos de Pipe, 21827, Venezuela ' Laboratorio de Ingeniería Térmica e Hidráulica Aplicada, ESIME Zacatenco, Instituto Politécnico Nacional (IPN), Av. Luis Enrique Erro S/N, Gustavo A. Madero, Zacatenco, 07730 Ciudad de México, Mexico; Laboratorio de Física de Fluidos y Plasmas, Instituto Venezolano de Investigaciones Científicas (IVIC), Altos de Pipe, 21827, Venezuela ' Departamento de Matematicas, Escuela Superior Politécnica del Litoral (ESPOL), ESPOL Polytechnic University, 30.5 km, Vía Perimetral Guayaquil, 09-01-5863, Ecuador ' Departamento de Matematicas, Escuela Superior Politécnica del Litoral (ESPOL), ESPOL Polytechnic University, 30.5 km, Vía Perimetral Guayaquil, 09-01-5863, Ecuador

Abstract: Nearest neighbour searching is central to the efficiency of smoothed particle hydrodynamics (SPH). Here the performance of the brute force (BF) or direct search (DS), the cell-linked list (CLL), and the KD-tree (KDT) methods in vectorised form are analysed. The results indicate that the efficiency of the SPH calculations is improved with the vectorised cell-linked list (VCLL) and the vectorised KD-tree (VKDT). However, the VKDT approach is more efficient than the VCLL method for N ≤ 10⁵ in two dimensions (2D) and N ≤ 10⁶ in three dimensions (3D). For larger N, the time duration of the SPH calculations with the VKDT method grows steeply while a linear trend is maintained with the VCLL. The complexity here is measured not only for early events but also close to the point of hardware limit, in which the complexity has a different behaviour, which can be measured and compared using a power fit.

Keywords: nearest neighbour search; closest pair search; data structures; smoothed particle hydrodynamics; SPH.

DOI: 10.1504/PCFD.2021.112625

Progress in Computational Fluid Dynamics, An International Journal, 2021 Vol.21 No.1, pp.1 - 18

Received: 02 Aug 2019
Accepted: 18 Jun 2020
Published online: 25 Jan 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article