Slepian, Zachary and Eisenstein, Daniel J. 2015. "Computing the three-point correlation function of galaxies in O(N^2) time." Monthly Notices of the Royal Astronomical Society 454:4142-4158. https://doi.org/10.1093/mnras/stv2119
We present an algorithm that computes the multipole coefficients of the galaxy three-point correlation function (3PCF) without explicitly considering triplets of galaxies. Rather, centring 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 run-times 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 catalogues, computing an edge corrected 3PCF out to 90 Mpc h-1 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, Large Synoptic Survey Telescope (LSST), and Dark Energy Spectroscopic Instrument.
