Computing the Three-Point Correlation Function of Galaxies in $\mathcal{O}(N^2)$ Time

Abstract

We present an algorithm that computes the multipole coefficients of the galaxy three-point correlation function (3PCF) without explicitly considering triplets of galaxies. Rather, centering on each galaxy in the survey, it expands the radially-binned density field in spherical harmonics and combines these to form the multipoles without ever requiring the relative angle between a pair about the central. This approach scales with number and number density in the same way as the two-point correlation function, allowing runtimes that are comparable, and 500 times faster than a naive triplet count. It is exact in angle and easily handles edge correction. We demonstrate the algorithm on the LasDamas SDSS-DR7 mock catalogs, computing an edge corrected 3PCF out to $90\mathrm{Mpc}/h$ in under an hour on modest computing resources. We expect this algorithm will render it possible to obtain the large-scale 3PCF for upcoming surveys such as Euclid, LSST, and DESI.

21 pages, 12 figures, accepted MNRAS with minor revisions; v2 matches accepted version

References in corpus (7)

• The Effect of Large-Scale Structure on the SDSS Galaxy Three-Point Correlation Function
• Three-Point Correlation Functions of SDSS Galaxies: Luminosity and Color Dependence in Redshift and Projected Space
• Accelerating the 2-point and 3-point galaxy correlation functions using Fourier transforms
• On the signature of the baryon-dark matter relative velocity in the two and three-point galaxy correlation functions
• Modelling The Redshift-Space Three-Point Correlation Function in SDSS-III
• Fast n-point correlation functions and three-point lensing application
• A Robust Estimator of the Small-Scale Galaxy Correlation Function

Cited by in corpus (78)

• Euclid. I. Overview of the Euclid mission
• nbodykit: an open-source, massively parallel toolkit for large-scale structure
• Learning to Predict the Cosmological Structure Formation
• Detection of Baryon Acoustic Oscillation Features in the Large-Scale 3-Point Correlation Function of SDSS BOSS DR12 CMASS Galaxies
• Probing Parity-Violation with the Four-Point Correlation Function of BOSS Galaxies
• The large-scale 3-point correlation function of the SDSS BOSS DR12 CMASS galaxies
• An optimal FFT-based anisotropic power spectrum estimator
• A complete FFT-based decomposition formalism for the redshift-space bispectrum
• Measurement of Parity-Odd Modes in the Large-Scale 4-Point Correlation Function of SDSS BOSS DR12 CMASS and LOWZ Galaxies
• Testing the theory of gravity with DESI: estimators, predictions and simulation requirements
• A Detection of the Baryon Acoustic Oscillation Features in the SDSS BOSS DR12 Galaxy Bispectrum
• Accelerating the 2-point and 3-point galaxy correlation functions using Fourier transforms
• Accurate and Efficient Halo-based Galaxy Clustering Modelling with Simulations
• Modeling the large-scale redshift-space 3-point correlation function of galaxies
• A Practical Computational Method for the Anisotropic Redshift-Space 3-Point Correlation Function
• Mitigating contamination in LSS surveys: a comparison of methods
• Capturing Non-Gaussianity of the Large-Scale Structure with Weighted Skew-Spectra
• ENCORE: An $\mathcal{O}(N_{\mathrm{g}}^2)$ Estimator for Galaxy $N$-Point Correlation Functions
• FFT-PT: Reducing the two-loop large-scale structure power spectrum to low-dimensional radial integrals
• Classification of Magnetohydrodynamic Simulations using Wavelet Scattering Transforms
• Constraining the Baryon-Dark Matter Relative Velocity with the Large-Scale 3-Point Correlation Function of the SDSS BOSS DR12 CMASS Galaxies
• Power spectrum multipoles on the curved sky: an application to the 6-degree Field Galaxy Survey
• Information Content of Higher-Order Galaxy Correlation Functions
• Estimating the galaxy two-point correlation function using a split random catalog
• Towards a self-consistent analysis of the anisotropic galaxy two- and three-point correlation functions on large scales: application to mock galaxy catalogues
• Estimating Covariance Matrices for Two- and Three-Point Correlation Function Moments in Arbitrary Survey Geometries
• Computing the Small-Scale Galaxy Power Spectrum and Bispectrum in Configuration-Space
• Disconnected Covariance of 2-point Functions in Large-Scale Structure
• Analytic Gaussian Covariance Matrices for Galaxy $N$-Point Correlation Functions
• Isotropic N-Point Basis Functions and Their Properties
• Developing the 3-Point Correlation Function For the Turbulent Interstellar Medium
• Graph Database Solution for Higher Order Spatial Statistics in the Era of Big Data
• New constraints on cosmological modified gravity theories from anisotropic three-point correlation functions of BOSS DR12 galaxies
• Efficient Computation of $N$-point Correlation Functions in $D$ Dimensions
• C${}^3$-Cluster Clustering Cosmology II. First detection of the BAO peak in the three-point correlation function of galaxy clusters
• A Faster Fourier Transform? Computing Small-Scale Power Spectra and Bispectra for Cosmological Simulations in $\mathcal{O}(N^2)$ Time
• No evidence for parity violation in BOSS
• The Catalogue for Astrophysical Turbulence Simulations (CATS)
• Towards cosmological constraints from the compressed modal bispectrum: a robust comparison of real-space bispectrum estimators
• Optimal computation of anisotropic galaxy three point correlation function multipoles using 2DFFTLOG formalism
• Modeling the Marked Spectrum of Matter and Biased Tracers in Real- and Redshift-Space
• Cosmological Probes of Structure Growth and Tests of Gravity
• Bispectrum as Baryon Acoustic Oscillation Interferometer
• Testing the consistency of three-point halo clustering in Fourier and configuration space
• A roadmap to cosmological parameter analysis with third-order shear statistics III: Efficient estimation of third-order shear correlation functions and an application to the KiDS-1000 data
• Cosmic Web Dissection in Fuzzy Dark Matter Cosmologies
• Modelling the next-to-leading order matter three-point correlation function using FFTLog
• Probing high order dependencies with information theory
• A joint 2- and 3-point clustering analysis of the VIPERS PDR2 catalogue at z~1: breaking the degeneracy of cosmological parameters
• The $n$-point streaming model: how velocities shape correlation functions in redshift space
• Higher multipoles of the galaxy bispectrum in redshift space
• Fast Correlation Function Calculator -- A high-performance pair counting toolkit
• Impact of tidal environment on galaxy clustering in GAMA
• On the Fast Random Sampling and Other Properties of the Three Point Correlation Function in Galaxy Surveys
• KiDS-Legacy: Covariance validation and the unified OneCovariance framework for projected large-scale structure observables
• The halo 3-point correlation function: a methodological analysis
• On the galaxy 3-point correlation function in Modified Gravity
• Constraining galaxy-halo connection with high-order statistics
• Computing 3 point correlation function randoms counts without the randoms catalogue
• Triumvirate: A Python/C++ package for three-point clustering measurements
• Triple-Spherical Bessel Function Integrals with Exponential and Gaussian Damping: Towards an Analytic N-Point Correlation Function Covariance Model
• ConKer: evaluating isotropic correlations of arbitrary order
• Galactos: Computing the Anisotropic 3-Point Correlation Function for 2 Billion Galaxies
• Breaking parity: the case of the trispectrum from chiral scalar-tensor theories of gravity
• Studying Interstellar Turbulence Driving Scales using the Bispectrum
• Projected two- and three-point statistics: Forecasts and mitigation of non-linear RSDs
• Structure in Galaxy Distribution. III. Fourier Transforming the Universe
• Non-Gaussian statistics in galaxy weak lensing: compressed three-point correlations and cosmological forecasts
• The imprints of massive neutrinos on the three-point correlation function of large-scale structures
• Confusion noise due to clustered extragalactic point sources. Application of logarithmic cumulants for parameter estimation
• Modeling and measuring the anisotropic halo 3-point correlation function: a coordinated study
• Weak lensing deflection of three-point correlation functions
• Three-point intrinsic alignments of galaxies and haloes in the FLAMINGO simulations
• Parity-odd Four-Point Correlation Function from DESI Data Release 1 Luminous Red Galaxy Sample
• nuGAN: Generative Adversarial Emulator for Cosmic Web with Neutrinos
• An Optimal In-Situ Multipole Algorithm for the Isotropic Three-Point Correlation Functions
• Lya2pcf: an efficient pipeline to estimate two- and three-point correlation functions of the Lyman-$\alpha$ forest
• Euclid preparation. Full-shape modelling of 2-point and 3-point correlation functions in real space