ENCORE: An $\mathcal{O}(N_{\rm g}^2)$ Estimator for Galaxy $N$-Point Correlation Functions

Understand

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_{\rm g}^2)$ for $N_{\rm g}$ particles, or $\mathcal{O}\left(N_\mathrm{FFT}\log N_\mathrm{FFT}\right)$ when using a Fast Fourier Transform with $N_\mathrm{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.