Astronomers Presented An Algorithm Which Computes N-point Correlation Functions Faster Than Any (Cosmology / Instrumentation)

Ever wanted to do cosmology from the four-point or the five-point function? Oliver Philcox and colleagues introduced a new estimator which computes the N-point galaxy correlation functions of Ng galaxies in O(Ng^2) time, *far* faster than the naive O(Ng^N) scaling!

𝑁-point correlation functions (NPCFs), or their Fourier-space counterparts, the polyspectra, are amongst the most powerful tools in the survey analyst’s workshop. These encode the statistical properties of the galaxy overdensity field at sets of 𝑁 positions, and may be compared to data to give constraints on properties such as the Universe’s expansion rate and composition.

Most inflationary theories predict density fluctuations in the early Universe to follow Gaussian statistics; in this case all the information is contained within the two-point correlation function (2PCF), or, equivalently, the power spectrum. For a homogeneous and isotropic Universe, both are simple functions of one variable, and have been the subject of almost all galaxy survey analyses to date.

The late-time Universe is far from Gaussian. Statistics beyond the 2PCF are of importance since the bulk motion of matter in structure formation causes a cascade of information from the 2PCF to higher-order statistics, such as the three- and four-point functions (3PCF and 4PCF).

“Correlation functions form the cornerstone of modern cosmology, and their efficient computation is a task of utmost importance for the analysis of current and future galaxy surveys.”

Now, Oliver Philcox and colleagues presented a new estimator/algorithm for efficiently computing the N-point galaxy correlation functions of Ng galaxies in O(Ng^2) time, *far* faster than the naive O(Ng^N) scaling!

By decomposing the N-point correlation function (NPCF) into an angular basis composed of products of spherical harmonics, the estimator becomes *separable* in r1, r2, r3, etc. It can be computed as a weighted sum of *pairs* of galaxies, for any N.

© Oliver Philcox et al

The algorithm is included in their new code *encore*: https://github.com/oliverphilcox/encore

It is written in C++ and computes the 3PCF, 4PCF, 5 PCF and 6 PCF of a BOSS-like galaxy survey in ~ 100 CPU-hours, including applying corrections for the non-uniform survey geometry. It can also be run on a GPU!

Whilst the complexity is technically O(Ng^2), for N>3, they practically found computation-time to scale *linearly* with the number of galaxies unless the density is very large! Below figure is the measurement of a few 5PCF components:

© Oliver Philcox et al.

This will allow future surveys like Euclid, DESI, and Roman to include higher-point functions in their analyses, giving sharper constraints on cosmological parameters, and testing new physics such as parity-violation!

Featured image: Strong scaling of the encore code: dependence of runtime, 𝑇 , on the number of CPU cores on a single node for different test cases. Dashed lines indicate linear relationships, and are calibrated at the single-CPU time © Philcox et al.


Reference: Oliver H. E. Philcox, Zachary Slepian, Jiamin Hou, Craig Warner, Robert N. Cahn, Daniel J. Eisenstein, “ENCORE: Estimating Galaxy N-point Correlation Functions in O(N2g) Time”, Arxiv, pp. 1-24, 2021. https://arxiv.org/abs/2105.08722


Note for editors of other websites: To reuse this article fully or partially kindly give credit either to our author/editor S. Aman or provide a link of our article

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s