Encore: an O (Ng2) estimator for galaxy N-point correlation functions. Issue 2 (20th October 2021)

• Record Type: Journal Article
• Authors: Philcox, Oliver H E; Slepian, Zachary; Hou, Jiamin; Warner, Craig; Cahn, Robert N; Eisenstein, Daniel J
• Is Part Of: Monthly notices of the Royal Astronomical Society. Volume 509:Issue 2(2022)
• Page Start: 2457
• Page End: 2481
• Publication Date: 2021-10-20
• Subjects: methods: numerical -- methods: statistical -- galaxies: statistics -- large-scale structure of Universe -- cosmology: theory; Astronomy -- Periodicals; Periodicals; 520.5
• DOI: 10.1093/mnras/stab3025
• Languages: English
• ISSNs: 0035-8711

Abstract

ABSTRACT: We present a new algorithm for efficiently computing the N -point correlation functions (NPCFs) of a 3D density field for arbitrary N . This can be applied both to a discrete spectroscopic galaxy survey and a continuous field. By expanding the statistics in a separable basis of isotropic functions built from spherical harmonics, the NPCFs can be estimated by counting pairs of particles in space, leading to an algorithm with complexity $\mathcal {O}(N_\mathrm{g}^2)$ for N g particles, or $\mathcal {O}(N_\mathrm{FFT}\log N_\mathrm{FFT})$ when using a Fast Fourier Transform with N FFT grid-points. In practice, the rate-limiting step for N > 3 will often be the summation of the histogrammed spherical harmonic coefficients, particularly if the number of radial and angular bins is large. In this case, the algorithm scales linearly with N g . The approach is implemented in the encore code, which can compute the 3PCF, 4PCF, 5PCF, and 6PCF of a BOSS-like galaxy survey in ${\sim}100$ CPU-hours, including the corrections necessary for non-uniform survey geometries. We discuss the implementation in depth, along with its GPU acceleration, and provide practical demonstration on realistic galaxy catalogues. Our approach can be straightforwardly applied to current and future data sets to unlock the potential of constraining cosmology from the higher point functions.