nifty-ls: Fast and Accurate Lomb–Scargle Periodograms Using a Non-uniform FFT

Lehman H. Garrison, Daniel Foreman-Mackey, Yu-hsuan Shih, Alex H. Barnett

TL;DR

This paper introduces nifty-ls, a new Python package that dramatically speeds up and improves the accuracy of Lomb-Scargle periodograms, a crucial tool for finding periodic signals in astronomical data. By leveraging a non-uniform Fast Fourier Transform (NUFFT) and offering GPU acceleration, nifty-ls is orders of magnitude faster and more accurate than existing methods, making it a valuable asset for astronomers.

What Problem Does This Paper Address?

Astronomers frequently analyze time-series data – sequences of measurements taken over time – to detect periodic signals, such as the rotation of stars or the orbital periods of exoplanets. The Lomb-Scargle periodogram is a standard statistical method for this task, particularly effective for unevenly sampled data (where observations aren't taken at perfectly regular intervals). However, the direct computation of the Lomb-Scargle periodogram is computationally expensive, with a time complexity of O(N_d * N_f), where N_d is the number of data points and N_f is the number of frequencies to check. While previous methods like the Press & Rybicki (PR89) algorithm offered improvements by using Fast Fourier Transforms (FFTs) on interpolated data, they still faced limitations in speed and accuracy, especially for large datasets. This paper addresses the need for a faster, more accurate, and easily accessible tool for Lomb-Scargle periodogram computation.

Methods

The core innovation of nifty-ls lies in its reformulation of the Lomb-Scargle periodogram calculation as a Non-Uniform Fast Fourier Transform (NUFFT). The authors recognize that the trigonometric sums involved in the periodogram are precisely what a NUFFT is designed to compute efficiently, even with unevenly sampled data. They utilize the Flatiron Institute's NUFFT package (FINUFFT) as their backend, which employs a sophisticated spreading kernel for high accuracy and speed.

Key aspects of their method include:

  • NUFFT Formulation: Directly applying NUFFT to the observation times and weights, avoiding the data interpolation step of previous methods.
  • FINUFFT Backend: Leveraging FINUFFT's optimized algorithms for both CPU (including multi-threading) and GPU (via CUDA) computations.
  • ASTROPY Integration: Providing a backend option for the popular ASTROPY library, allowing users to seamlessly switch to nifty-ls with minimal code changes.
  • Open-Source Availability: Making the software publicly available on GitHub and providing binary distributions on PyPI for easy adoption.

Datasets

The paper does not introduce new datasets for training. Instead, it uses synthetic time-series data with varying numbers of observations (N_d) ranging from 10^2 to 10^6. The number of frequencies (N_f) is set to approximately 12 times the number of observations (N_f ≈ 12N_d), which is a standard setting in ASTROPY. This setup allows for a comprehensive evaluation of performance and accuracy across a wide range of data sizes.

Key Insights and Ideas

  • NUFFT is a Natural Fit: The most significant insight is the realization that the Lomb-Scargle periodogram's core equations are directly solvable by a NUFFT, offering a more principled and efficient approach than FFTs on interpolated data.
  • Accuracy Gains are Dramatic: The NUFFT approach, particularly with FINUFFT's advanced kernels, leads to accuracy improvements of orders of magnitude compared to existing FFT-based methods. This is crucial for robust scientific discovery.
  • GPU Acceleration is a Game-Changer: The integration of CUDA-based NUFFT (CUFINUFFT) provides substantial speedups, making it feasible to analyze much larger datasets or perform more extensive searches in a reasonable time.
  • Performance Scales Well: The performance of nifty-ls scales favorably with the number of observations, demonstrating significant speedups as dataset sizes increase.

Key Results

  • Speed: nifty-ls is several times faster than ASTROPY's fast method on a single CPU thread, with speedups reaching up to 5x for large datasets. With CPU multi-threading, speedups of up to 11x are observed. On GPUs, nifty-ls is up to 200x faster than ASTROPY for large N_d.
  • Accuracy: nifty-ls achieves median relative errors of 10^-11 to 10^-8 and 99th percentile errors of 10^-8 to 10^-6. This is a stark contrast to ASTROPY's fast method, which shows median errors around 0.1% and 99th percentile errors that can reach 10% or higher in worst-case scenarios.
  • Efficiency: The package can process approximately 10^7 output frequencies per second on a CPU and 10^8 on a GPU.

Limitations and Future Work

  • Double Precision Recommended: The authors recommend using double-precision floating-point numbers for calculations, as single precision can lead to significantly larger errors, especially for large transforms. This is due to the inherent condition number of the problem.
  • GPU Overhead for Small Datasets: For very small numbers of observations (N_d), the overhead of GPU computation can negate the speed benefits. However, even for N_d as small as 4000, there's a benefit over CPU-only FINUFFT.
  • Future Work: The paper mentions that nifty-ls can produce lower-precision results slightly faster, implying potential for further optimization by trading off some accuracy for speed. The authors also suggest that the ASTROPY integration and availability of binary distributions lower the barrier to adoption, hinting at a future where this improved method becomes standard.

Summary updated

Abstract

Abstract We present nifty-ls , a software package for fast and accurate evaluation of the Lomb–Scargle periodogram. nifty-ls leverages the fact that Lomb–Scargle can be computed using a non-uniform fast Fourier transform (NUFFT), which we evaluate with the Flatiron Institute NUFFT package ( finufft ). This approach achieves a many-fold speedup over the Press & Rybicki method as implemented in Astropy and is simultaneously many orders of magnitude more accurate. nifty-ls also supports fast evaluation on GPUs via CUDA and integrates with the Astropy Lomb–Scargle interface. nifty-ls is publicly available at https://github.com/flatironinstitute/nifty-ls/ .
BibTeX
@inproceedings{garrison2024nifty,
  author = {Lehman H. Garrison and Daniel Foreman-Mackey and Yu-hsuan Shih and Alex H. Barnett},
  title = {{nifty-ls: Fast and Accurate Lomb–Scargle Periodograms Using a Non-uniform FFT}},
  booktitle = {Research Notes of the AAS},
  year = {2024},
  doi = {10.3847/2515-5172/ad82cd},
}
Figure