A Faster Fourier Transform? Computing Small-Scale Power Spectra and Bispectra for Cosmological Simulations in $mathcal{O}(N^2)$ Time. (arXiv:2005.01739v3 [astro-ph.CO] UPDATED)
<a href="http://arxiv.org/find/astro-ph/1/au:+Philcox_O/0/1/0/all/0/1">Oliver H.E. Philcox</a>

We present $mathcal{O}(N^2)$ estimators for the small-scale power spectrum
and bispectrum in cosmological simulations. In combination with traditional
methods, these allow spectra to be efficiently computed across a vast range of
scales, requiring orders of magnitude less computation time than Fast Fourier
Transform based approaches alone. These methods are applicable to any tracer;
simulation particles, halos or galaxies, and take advantage of the simple
geometry of the box and periodicity to remove almost all dependence on large
random particle catalogs. By working in configuration-space, both power spectra
and bispectra can be computed via a weighted sum of particle pairs up to some
radius, which can be reduced at larger $k$, leading to algorithms with
decreasing complexity on small scales. These do not suffer from aliasing or
shot-noise, allowing spectra to be computed to arbitrarily large wavenumbers.
The estimators are rigorously derived and tested against simulations, and their
covariances discussed. The accompanying code, HIPSTER, has been publicly
released, incorporating these algorithms. Such estimators will be of great use
in the analysis of large sets of high-resolution simulations.

We present $mathcal{O}(N^2)$ estimators for the small-scale power spectrum
and bispectrum in cosmological simulations. In combination with traditional
methods, these allow spectra to be efficiently computed across a vast range of
scales, requiring orders of magnitude less computation time than Fast Fourier
Transform based approaches alone. These methods are applicable to any tracer;
simulation particles, halos or galaxies, and take advantage of the simple
geometry of the box and periodicity to remove almost all dependence on large
random particle catalogs. By working in configuration-space, both power spectra
and bispectra can be computed via a weighted sum of particle pairs up to some
radius, which can be reduced at larger $k$, leading to algorithms with
decreasing complexity on small scales. These do not suffer from aliasing or
shot-noise, allowing spectra to be computed to arbitrarily large wavenumbers.
The estimators are rigorously derived and tested against simulations, and their
covariances discussed. The accompanying code, HIPSTER, has been publicly
released, incorporating these algorithms. Such estimators will be of great use
in the analysis of large sets of high-resolution simulations.

http://arxiv.org/icons/sfx.gif