Efficient computation of <i>N</i> -point correlation functions in <i>D</i> dimensions
Oliver H. E. Philcox, Zachary Slepian
Abstract
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. Typically, algorithms for computing the NPCF components have <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mi mathvariant="script">O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mi>N</mml:mi> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> complexity (for a dataset 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mi mathvariant="script">O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> or <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mi mathvariant="script">O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>n</mml:mi> <mml:mtext>g</mml:mtext> </mml:msub> <mml:mi>log</mml:mi> <mml:mo> </mml:mo> <mml:msub> <mml:mi>n</mml:mi> <mml:mtext>g</mml:mtext> </mml:msub> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> if evaluated using a Fast Fourier Transform on a grid of size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:msub> <mml:mi>n</mml:mi> <mml:mtext>g</mml:mtext> </mml:msub> </mml:mrow> </mml:math> . Our decomposition is built upon the D -dimensional hyperspherical harmonics; these form a complete basis on the <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>D</mml:mi> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> sphere and are intrinsically related to angular momentum operators. Concatenation of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>N</mml:mi> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> such harmonics gives states of definite combined angular momentum, forming a natural separable basis for the NPCF. As N and D 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.