Fast n-point correlation functions and three-point lensing application

Abstract

We present a new algorithm to rapidly compute the two-point (2PCF), three-point (3PCF) and n-point (n-PCF) correlation functions in roughly O(N log N) time for N particles, instead of O(N^n) as required by brute force approaches. The algorithm enables an estimate of the full 3PCF for as many as 10^6 galaxies. This technique exploits node-to-node correlations of a recursive bisectional binary tree. A balanced tree construction minimizes the depth of the tree and the worst case error at each node. The algorithm presented in this paper can be applied to problems with arbitrary geometry. We describe the detailed implementation to compute the two point function and all eight components of the 3PCF for a two-component field, with attention to shear fields generated by gravitational lensing. We also generalize the algorithm to compute the n-point correlation function for a scalar field in k dimensions where n and k are arbitrary positive integers.

37 pages, 6 figures, LaTeX; added and modified figures, modified theoretical estimate of computing time; accepted by New Astronomy

References in corpus (8)

• The 2dF Galaxy Redshift Survey: The bias of galaxies and the density of the Universe
• Detection of weak gravitational lensing distortions of distant galaxies by cosmic dark matter at large scales
• Detection of dark matter Skewness in the VIRMOS-DESCART survey: Implications for Ω_0
• The three-point correlation function of cosmic shear: I. The natural components
• Fast Algorithms and Efficient Statistics: N-point Correlation Functions
• Mining Weak Lensing Surveys
• Fast Power Spectrum Estimation
• The Complete Bispectrum of COBE-DMR Four Year Maps

Cited by in corpus (22)

• Computing the Three-Point Correlation Function of Galaxies in $\mathcal{O}(N^2)$ Time
• Weak lensing from space: first cosmological constraints from three-point shear statistics
• Optimal capture of non-Gaussianity in weak lensing surveys: power spectrum, bispectrum and halo counts
• A Practical Computational Method for the Anisotropic Redshift-Space 3-Point Correlation Function
• Sources of contamination to weak lensing three-point statistics: constraints from N-body simulations
• ENCORE: An $\mathcal{O}(N_{\mathrm{g}}^2)$ Estimator for Galaxy $N$-Point Correlation Functions
• GaBoDS: The Garching-Bonn Deep Survey: VII. Probing galaxy bias using weak gravitational lensing
• Precision measurement of cosmic magnification from 21 cm emitting galaxies
• Measurement of the Cold Dark Matter-Neutrino Dipole in the TianNu Simulation
• Estimating Covariance Matrices for Two- and Three-Point Correlation Function Moments in Arbitrary Survey Geometries
• Graph Database Solution for Higher Order Spatial Statistics in the Era of Big Data
• First detection of galaxy-galaxy-galaxy lensing in RCS. A new tool for studying the matter environment of galaxy pairs
• Measuring the Three Point Correlation Function of the Cosmic Microwave Background
• A First Detection of the Connected 4-Point Correlation Function of Galaxies Using the BOSS CMASS Sample
• Efficient Computation of $N$-point Correlation Functions in $D$ Dimensions
• CFHTLenS: A Gaussian likelihood is a sufficient approximation for a cosmological analysis of third-order cosmic shear statistics
• Fast Calculation of the Weak Lensing Aperture Mass Statistic
• 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
• A Fast and Accurate Analytic Method of Calculating Galaxy Two-point Correlation Functions
• Detecting unresolved moving sources in a diffuse background
• An Optimal In-Situ Multipole Algorithm for the Isotropic Three-Point Correlation Functions