Performance Enhancement of Tree-based Friends-of-friend Galaxy-finder for High-resolution Simulations of Galaxy Formation

Abstract

Cosmological simulations are useful tools for studying the evolution of galaxies, and it is critical to accurately identify galaxies and their halos from raw simulation data. The friends-of-friend (FoF) algorithm has been widely adopted for this purpose because of its simplicity and expandability to higher dimensions. However, it is cost-inefficient when applied to high-resolution simulations because standard FoF implementation leads to too many distance calculations in dense regions. We confirm this through our exercise of applying the 6-dimensional (6D) FoF galaxy finder code, VELOCIraptor (Elahi et al. 2019), on the NewHorizon simulation (Dubois et al. 2021). The high particle resolution of NewHorizon ($M_{\mathrm{star}}\sim 10^4{M}_{\odot }$) allows a large central number density ($10^6{\mathrm{kpc}}^{-3}$) for typical galaxies, resulting in a few days to weeks of galaxy searches for just one snapshot. Even worse, we observed a significant decrease in the FoF performance in the high-dimensional 6D searches: "the curse of dimensionality" problem. To overcome these issues, we have developed several implementations that can be readily applied to any tree-based FoF code. They include limiting visits to tree nodes, re-ordering the list of particles for searching neighbor particles, and altering the tree structure. Compared to the run with the original code, the new run with these implementations results in the identical galaxy detection with the ideal performance, $O(N\log N)$, $N$ being the number of particles in a galaxy -- with a speed gain of a factor of 2700 in 3D or 12 in 6D FoF search.

arXiv comment24 pages, 16 figures, and 2 tables. Accepted for publication in ApJ

References in corpus (29)

• Seven-Year Wilkinson Microwave Anisotropy Probe (WMAP) Observations: Cosmological Interpretation
• The cosmological simulation code GADGET-2
• Simulating the joint evolution of quasars, galaxies and their large-scale distribution
• The EAGLE project: Simulating the evolution and assembly of galaxies and their environments
• Populating a cluster of galaxies - I. Results at z=0
• Introducing the Illustris Project: Simulating the coevolution of dark and visible matter in the Universe
• Cosmological Hydrodynamics with Adaptive Mesh Refinement: a new high resolution code called RAMSES
• The Rockstar Phase-Space Temporal Halo Finder and the Velocity Offsets of Cluster Cores
• FIRE-2 Simulations: Physics versus Numerics in Galaxy Formation
• Substructures in hydrodynamical cluster simulations
• Ahf: Amiga's Halo Finder
• Dancing in the dark: galactic properties trace spin swings along the cosmic web
• Haloes gone MAD: The Halo-Finder Comparison Project
• Simulating cosmic structure formation with the GADGET-4 code
• The origin and implications of dark matter anisotropic cosmic infall on ~L* haloes
• Introducing the NewHorizon simulation: Galaxy properties with resolved internal dynamics across cosmic time
• Structure Finding in Cosmological Simulations: The State of Affairs
• The overdensity and masses of the friends-of-friends halos and universality of the halo mass function
• Cold Dark Matter I: The Formation of Dark Halos
• Hunting for Galaxies and Halos in simulations with VELOCIraptor
• SURFS: Riding the waves with Synthetic UniveRses For Surveys
• Introducing a new, robust galaxy finder algorithm for simulations
• The impact of stellar and AGN feedback on halo-scale baryonic and dark matter accretion in the EAGLE simulations
• Cosmological baryon transfer in the SIMBA simulations
• Galaxies going MAD: The Galaxy-Finder Comparison Project
• Pre-processing, group accretion and the orbital trajectories of associated subhaloes
• Climbing Halo Merger Trees with TreeFrog
• nIFTy Galaxy Cluster simulations VI: The dynamical imprint of substructure on gaseous cluster outskirts
• Tree-less 3d Friends-of-Friends using Spatial Hashing