Efficient Computation of $N$-point Correlation Functions in $D$ Dimensions

Understand

We present efficient algorithms for computing the $N$-point correlation functions (NPCFs) of random fields in arbitrary $D$-dimensional homogeneous and isotropic spaces.

• Such statistics appear throughout the physical sciences, and provide a natural tool to describe stochastic processes.
• algorithms for computing the NPCF components have $\mathcal{O}(n^N)$ complexity (for a data set containing $n$ particles); their application is thus computationally infeasible unless $N$ is small.
• By projecting the statistic onto a suitably-defined angular basis, we show that the estimators can be written in a separable form, with complexity $\mathcal{O}(n^2)$, or $\mathcal{O}(n_{\rm g}\log n_{\rm g})$ if evaluated using a Fast Fourier Transform on a grid of size $n_{\rm g}$.