ENCORE: An $\mathcal{O}(N_{\mathrm{g}}^2)$ Estimator for Galaxy $N$-Point Correlation Functions

Abstract

We present a new algorithm for efficiently computing the $N$-point correlation functions (NPCFs) of a 3D density field for arbitrary $N$. This can be applied both to a discrete spectroscopic galaxy survey and a continuous field. By expanding the statistics in a separable basis of isotropic functions built from spherical harmonics, the NPCFs can be estimated by counting pairs of particles in space, leading to an algorithm with complexity $\mathcal{O}(N_{\mathrm{g}}^2)$ for $N_{\mathrm{g}}$ particles, or $\mathcal{O}\left(N_{\mathrm{FFT}}\log N_{\mathrm{FFT}}\right)$ when using a Fast Fourier Transform with $N_{\mathrm{FFT}}$ grid-points. In practice, the rate-limiting step for $N>3$ will often be the summation of the histogrammed spherical harmonic coefficients, particularly if the number of radial and angular bins is large. In this case, the algorithm scales linearly with $N_{\mathrm{g}}$. The approach is implemented in the ENCORE code, which can compute the 3PCF, 4PCF, 5PCF, and 6PCF of a BOSS-like galaxy survey in $\sim$ $100$ CPU-hours, including the corrections necessary for non-uniform survey geometries. We discuss the implementation in depth, along with its GPU acceleration, and provide practical demonstration on realistic galaxy catalogs. Our approach can be straightforwardly applied to current and future datasets to unlock the potential of constraining cosmology from the higher-point functions.

arXiv comment25 pages, 6 figures, accepted by MNRAS. Code available at https://github.com/oliverphilcox/encore

References in corpus (102)

• The clustering of galaxies in the completed SDSS-III Baryon Oscillation Spectroscopic Survey: cosmological analysis of the DR12 galaxy sample
• The Eleventh and Twelfth Data Releases of the Sloan Digital Sky Survey: Final Data from SDSS-III
• SDSS-III: Massive Spectroscopic Surveys of the Distant Universe, the Milky Way Galaxy, and Extra-Solar Planetary Systems
• The Baryon Oscillation Spectroscopic Survey of SDSS-III
• Large-Scale Structure of the Universe and Cosmological Perturbation Theory
• The Completed SDSS-IV extended Baryon Oscillation Spectroscopic Survey: Cosmological Implications from two Decades of Spectroscopic Surveys at the Apache Point observatory
• Observational Probes of Cosmic Acceleration
• Power Spectrum Analysis of Three-Dimensional Redshift Surveys
• A 2% Distance to z=0.35 by Reconstructing Baryon Acoustic Oscillations - I : Methods and Application to the Sloan Digital Sky Survey
• Improving Cosmological Distance Measurements by Reconstruction of the Baryon Acoustic Peak
• The Cosmological Analysis of the SDSS/BOSS data from the Effective Field Theory of Large-Scale Structure
• Cosmological Parameters from the BOSS Galaxy Power Spectrum
• The clustering of galaxies in the completed SDSS-III Baryon Oscillation Spectroscopic Survey: Anisotropic galaxy clustering in Fourier-space
• The clustering of galaxies in the SDSS-III Baryon Oscillation Spectroscopic Survey: RSD measurement from the power spectrum and bispectrum of the DR12 BOSS galaxies
• The clustering of galaxies in the SDSS-III Baryon Oscillation Spectroscopic Survey: mock galaxy catalogues for the BOSS Final Data Release
• Bayesian physical reconstruction of initial conditions from large scale structure surveys
• Linear Redshift Distortions: A Review
• Massive Lossless Data Compression and Multiple Parameter Estimation from Galaxy Spectra
• The clustering of galaxies in the completed SDSS-III Baryon Oscillation Spectroscopic Survey: Baryon Acoustic Oscillations in Fourier-space
• The power spectrum and bispectrum of SDSS DR11 BOSS galaxies I: bias and gravity
• Combining Full-Shape and BAO Analyses of Galaxy Power Spectra: A 1.6% CMB-independent constraint on H0
• Fast Estimators for Redshift-Space Clustering
• The clustering of galaxies in the SDSS-III Baryon Oscillation Spectroscopic Survey: Modeling the clustering and halo occupation distribution of BOSS-CMASS galaxies in the Final Data Release
• The Three-Point Correlation Function in Cosmology
• The Bispectrum: From Theory to Observations
• The Bispectrum of IRAS Galaxies
• Efficient Cosmological Analysis of the SDSS/BOSS data from the Effective Field Theory of Large-Scale Structure
• The Bispectrum in the Effective Field Theory of Large Scale Structure
• Constraining Primordial non-Gaussianity with Bispectrum and Power Spectum from Upcoming Optical and Radio Surveys
• Detection of Baryon Acoustic Oscillation Features in the Large-Scale 3-Point Correlation Function of SDSS BOSS DR12 CMASS Galaxies
• Measuring neutrino masses with large-scale structure: Euclid forecast with controlled theoretical error
• Modeling Biased Tracers at the Field Level
• Algorithms for bispectra: forecasting, optimal analysis, and simulation
• Constraining $M_{\nu }$ with the Bispectrum II: The Total Information Content of the Galaxy Bispectrum
• Reconstructing baryon oscillations
• Cosmological Perturbation Theory Using the FFTLog: Formalism and Connection to QFT Loop Integrals
• The One-Loop Matter Bispectrum in the Effective Field Theory of Large Scale Structures
• Computing the Three-Point Correlation Function of Galaxies in $\mathcal{O}(N^2)$ Time
• Towards optimal extraction of cosmological information from nonlinear data
• The large-scale 3-point correlation function of the SDSS BOSS DR12 CMASS galaxies
• A High-Fidelity Realization of the Euclid Code Comparison $N$-body Simulation with Abacus
• Generalized massive optimal data compression
• The Effect of Large-Scale Structure on the SDSS Galaxy Three-Point Correlation Function
• Eulerian BAO Reconstructions and N-Point Statistics
• A complete FFT-based decomposition formalism for the redshift-space bispectrum
• The clustering of galaxies in the completed SDSS-III Baryon Oscillation Spectroscopic Survey: theoretical systematics and Baryon Acoustic Oscillations in the galaxy correlation function
• The Three-point Correlation Function of Galaxies Determined from the Las Campanas Redshift Survey
• The 3-point function in large scale structure: redshift distortions and galaxy bias
• Primordial Non-Gaussianity from Biased Tracers: Likelihood Analysis of Real-Space Power Spectrum and Bispectrum
• A Detection of the Baryon Acoustic Oscillation Features in the SDSS BOSS DR12 Galaxy Bispectrum
• Fast Algorithms and Efficient Statistics: N-point Correlation Functions
• Three-point Correlation Functions of SDSS Galaxies in Redshift Space: Morphology, Color, and Luminosity Dependence
• The Three-point Correlation Function of Galaxies Determined from the 2dF Galaxy Redshift Survey
• The Trispectrum in the Effective Field Theory of Large Scale Structure
• Accelerating the 2-point and 3-point galaxy correlation functions using Fourier transforms
• Perturbation theory approach to predict the covariance matrices of the galaxy power spectrum and bispectrum in redshift space
• Fewer Mocks and Less Noise: Reducing the Dimensionality of Cosmological Observables with Subspace Projections
• Modeling Galaxies in Redshift Space at the Field Level
• The Three-point Correlation Function of Galaxies: Comparing Halo Occupation Models with Observations
• Reconstruction of primordial density fields
• Galaxy redshift-space bispectrum: the Importance of Being Anisotropic
• The Large-Scale 3-point correlation function of SDSS Luminous Red Galaxies
• Information Content of the Angular Multipoles of Redshift-Space Galaxy Bispectrum
• Joint analysis of anisotropic power spectrum, bispectrum and trispectrum: application to N-body simulations
• Rapid Separable Analysis of Higher Order Correlators in Large Scale Structure
• Modeling the large-scale redshift-space 3-point correlation function of galaxies
• Modeling the three-point correlation function
• A Practical Computational Method for the Anisotropic Redshift-Space 3-Point Correlation Function
• Maximal compression of the redshift space galaxy power spectrum and bispectrum
• New Optimised Estimators for the Primordial Trispectrum
• Information content in the redshift-space galaxy power spectrum and bispectrum
• Three-Point Statistics from a New Perspective
• Reconstruction of cosmological initial conditions from galaxy redshift catalogues
• Unbiased Cosmology Inference from Biased Tracers using the EFT Likelihood
• Fast n-point correlation functions and three-point lensing application
• Constraining the Baryon-Dark Matter Relative Velocity with the Large-Scale 3-Point Correlation Function of the SDSS BOSS DR12 CMASS Galaxies
• The EFT Likelihood for Large-Scale Structure
• Non-linear shrinkage estimation of large-scale structure covariance
• Information Content of Higher-Order Galaxy Correlation Functions
• Towards a self-consistent analysis of the anisotropic galaxy two- and three-point correlation functions on large scales: application to mock galaxy catalogues
• Estimating the galaxy two-point correlation function using a split random catalog
• Geometrical compression: a new method to enhance the BOSS galaxy bispectrum monopole constraints
• Estimating Covariance Matrices for Two- and Three-Point Correlation Function Moments in Arbitrary Survey Geometries
• Polypolar spherical harmonic decomposition of galaxy correlators in redshift space: Toward testing cosmic rotational symmetry
• Sigma-Eight at the Percent Level: The EFT Likelihood in Real Space
• Computing the Small-Scale Galaxy Power Spectrum and Bispectrum in Configuration-Space
• Higher N-point function data analysis techniques for heavy particle production and WMAP results
• 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
• Exploring the posterior surface of the large scale structure reconstruction
• Efficient Optimal Reconstruction of Linear Fields and Band-powers from Cosmological Data
• A First Detection of the Connected 4-Point Correlation Function of Galaxies Using the BOSS CMASS Sample
• General and consistent statistics for cosmological observations
• A Faster Fourier Transform? Computing Small-Scale Power Spectra and Bispectra for Cosmological Simulations in $\mathcal{O}(N^2)$ Time
• Primordial power spectrum and cosmology from black-box galaxy surveys
• Neutrino Mass Signatures in the Galaxy Bispectrum
• Optimal computation of anisotropic galaxy three point correlation function multipoles using 2DFFTLOG formalism
• Efficient parallel algorithm for estimating higher-order polyspectra
• The Phase Coherence of Interstellar Density Fluctuations
• On the Fast Random Sampling and Other Properties of the Three Point Correlation Function in Galaxy Surveys
• Computing 3 point correlation function randoms counts without the randoms catalogue
• Improving the Line of Sight for the Anisotropic 3-Point Correlation Function of Galaxies: Centroid and Unit-Vector-Average Methods Scaling as $\mathcal{O}(N^2)$

Cited by in corpus (24)

• Constraints on Multi-Field Inflation from the BOSS Galaxy Survey
• Probing Parity-Violation with the Four-Point Correlation Function of BOSS Galaxies
• Precision analysis of the redshift-space galaxy bispectrum
• Measurement of Parity-Odd Modes in the Large-Scale 4-Point Correlation Function of SDSS BOSS DR12 CMASS and LOWZ Galaxies
• Colliding Ghosts: Constraining Inflation with the Parity-Odd Galaxy Four-Point Function
• Cosmological Information in the Marked Power Spectrum of the Galaxy Field
• No evidence for parity violation in BOSS
• Cosmological Probes of Structure Growth and Tests of Gravity
• 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
• Fast Correlation Function Calculator -- A high-performance pair counting toolkit
• On the galaxy 3-point correlation function in Modified Gravity
• Constraining galaxy-halo connection with high-order statistics
• Hitting the mark: Optimising Marked Power Spectra for Cosmology
• Bayesian deep learning for cosmic volumes with modified gravity
• Anatomy of Parity-violating Trispectra in Galaxy Surveys
• 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
• Breaking parity: the case of the trispectrum from chiral scalar-tensor theories of gravity
• Non-Gaussian statistics in galaxy weak lensing: compressed three-point correlations and cosmological forecasts
• Pair Counting without Binning -- A New Approach to Correlation Functions in Clustering Statistics
• 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
• An Optimal In-Situ Multipole Algorithm for the Isotropic Three-Point Correlation Functions
• nuGAN: Generative Adversarial Emulator for Cosmic Web with Neutrinos