Tree-less 3d Friends-of-Friends using Spatial Hashing
arXiv:1805.04911 · doi:10.1016/j.ascom.2018.09.010
Abstract
I describe a fast algorithm for the identification of connected sets of points where the point-wise connections are determined by a fixed spatial distance - a task commonly referred to in the cosmological simulation community as Friends-of-Friends (FOF) group finding. This technique sorts particles into fine cells sufficiently compact to guarantee their cohabitants are linked, and uses locality sensitive hashing to search for neighbouring (blocks of) cells. Tests on N-body simulations of up to a billion particles exhibit speed increases of factors up to 20x compared with FOF via trees (a factor around 8 is typical), and is consistently complete in less than the time of a k-d tree construction, giving it an intrinsic advantage over tree-based methods. The code is open-source and available online at https://github.com/pec27/hfof .
arXiv commentAccepted in Astronomy and Computing. 11 pages, 5 figures, updated to match accepted version
References in corpus (20)
- E pur si muove: Galiliean-invariant cosmological hydrodynamical simulations on a moving mesh
- Modeling feedback from stars and black holes in galaxy mergers
- Mass function of dark matter halos
- The Rockstar Phase-Space Temporal Halo Finder and the Velocity Offsets of Cluster Cores
- A Multi-Code Analysis Toolkit for Astrophysical Simulation Data
- Using the Evolution of Clusters to Constrain Omega
- Scaling relations for galaxy clusters in the Millennium-XXL simulation
- Haloes gone MAD: The Halo-Finder Comparison Project
- The halo mass function from the dark ages through the present day
- nbodykit: an open-source, massively parallel toolkit for large-scale structure
- Evolution of the Mass Function of Dark Matter Haloes
- Simulating the Universe with MICE: The abundance of massive clusters
- Early supersymmetric cold dark matter substructure
- Imprints of dark energy on cosmic structure formation: II) Non-Universality of the halo mass function
- Low Redshift Baryon Acoustic Oscillation Measurement from the Reconstructed 6-degree Field Galaxy Survey
- Fast and accurate mock catalogue generation for low-mass galaxies
- Fast Algorithms and Efficient Statistics: N-point Correlation Functions
- Bayesian inference of cosmic density fields from non-linear, scale-dependent, and stochastic biased tracers
- Globular Clusters Formed within Dark Halos I: present-day abundance, distribution and kinematics
- ICE-COLA: fast simulations for weak lensing observables
Cited by in corpus (4)
- Simulating cosmic structure formation with the GADGET-4 code
- SWIFT: A modern highly-parallel gravity and smoothed particle hydrodynamics solver for astrophysical and cosmological applications
- A Hybrid MPI+Threads Approach to Particle Group Finding Using Union-Find
- Performance Enhancement of Tree-based Friends-of-friend Galaxy-finder for High-resolution Simulations of Galaxy Formation