Efficient computation of <i>N</i>-point correlation functions in <i>D</i> dimensions.

Abstract

We present efficient algorithms for computing the <i>N</i>-point correlation functions (NPCFs) of random fields in arbitrary <i>D</i>-dimensional homogeneous and isotropic spaces. Such statistics appear throughout the physical sciences and provide a natural tool to describe stochastic processes. Typically, algorithms for computing the NPCF components have [Formula: see text] complexity (for a dataset containing <i>n</i> particles); their application is thus computationally infeasible unless <i>N</i> 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 [Formula: see text] or [Formula: see text] if evaluated using a Fast Fourier Transform on a grid of size [Formula: see text]. Our decomposition is built upon the <i>D</i>-dimensional hyperspherical harmonics; these form a complete basis on the [Formula: see text] sphere and are intrinsically related to angular momentum operators. Concatenation of [Formula: see text] such harmonics gives states of definite combined angular momentum, forming a natural separable basis for the NPCF. As <i>N</i> and <i>D</i> grow, the number of basis components quickly becomes large, providing a practical limitation to this (and all other) approaches: However, the dimensionality is greatly reduced in the presence of symmetries; for example, isotropic correlation functions require only states of zero combined angular momentum. We provide a Julia package implementing our estimators and show how they can be applied to a variety of scenarios within cosmology and fluid dynamics. The efficiency of such estimators will allow higher-order correlators to become a standard tool in the analysis of random fields.