Faster chi squared periodogram: Accelerating linear algebra with fast Toeplitz solvers

arXiv:2611.20300 · astro-ph.IM · Submitted 2026-11-15 · Read on arXiv

astro-ph.IM

Submitted: 2026-11-15

Updated: 2026-11-17

Comments: 10 pages, 9 figures, 3 tables

License: http://creativecommons.org/licenses/by/4.0/

The gist: In recent years, the traditional Lomb--Scargle periodogram, relying on least-squares fitting of a sinusoid to data with a known mean…

Abstract

In recent years, the traditional Lomb--Scargle periodogram, relying on least-squares fitting of a sinusoid to data with a known mean, has been mostly superseded by its floating-mean extension---the generalized Lomb--Scargle periodogram---due to the superior robustness and accuracy of the latter. While further generalization to higher-degree trigonometric polynomials (known as the multiharmonic analysis of variance and the fast χ squared periodogram) has been known for decades, its usage remains relatively uncommon, mostly due to its significantly higher computational cost. Here we present a technique reducing the computational complexity of such an extension by combining a Toeplitz formulation of the system of normal equations with non-uniform fast Fourier transforms, coupled with condition-number monitoring to protect against numerical instability. When modified for practical efficiency rather than asymptotic computational complexity, our approach reaches speed-ups exceeding an order of magnitude over current state-of-the-art implementations across a wide range of hyperparameters when evaluated on multithreaded systems, while matching or exceeding their accuracy. Additionally, we provide a reference implementation used for benchmarking, along with the code used to generate the results presented in this work.

Related papers