betaFeedback

WorksPhysics and Astronomy

Faster χ2χ^2 periodogram: Accelerating linear algebra with fast Toeplitz solvers

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 χ2χ^2 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.

Introduction

The Lomb–Scargle periodogram ([21, 29]) is among the most widely used tools in astronomical time-series analysis, largely owing to its computational efficiency. Both formulations are mathematically equivalent up to normalization and rely on least-squares fitting of a zero-mean sinusoid to irregularly sampled data.

Although such approaches are often sufficient to detect periodic variability, they are limited by their assumption that the mean value of the data equals the average value of the fitted model. This limitation was partially resolved by floating-mean periodograms (e.g., [30, 34]), whose computational cost is directly comparable to that of their zero-mean counterparts, while offering improved frequency determination and reduced susceptibility to aliasing.

Despite these advantages, the practical application of floating-mean periodograms remains limited by the assumption of sinusoidal variability. While multiharmonic extensions of these periodograms—the multiharmonic analysis of variance (AoVMH) and the fast χ2\chi^2 periodogram—have been known for decades and offer increased robustness and accuracy ([30, 24]), their adoption has remained limited, partly due to their computational cost. In general, naïve least-squares fitting of a degree-dd trigonometric polynomial (equivalent to fitting a Fourier series truncated at dd harmonics to a light curve containing MM measurements) across NN frequency nodes requires O(dN(M+d2))O(dN(M+d^2)) operations. To reduce this computational burden, two fast algorithms have been developed. The Szegő recursion approach shown by

Schwarzenberg-Czerny [30] allows an exact solution of such a system to be derived in O(dNM)O(dNM) operations by omitting the dense linear solve; however, because the sums are evaluated directly in the time domain, its cost still scales linearly with MM per trial frequency. An alternative approach achieves an arbitrary-precision approximation by evaluating the trigonometric sums via a single type-1 non-uniform fast Fourier transform (NuFFT-1; [24]), allowing the algorithm to achieve a computational complexity of O(dN(log⁡N+d2))O(dN(\log N+d^2)), sublinear with respect to MM, at the cost of retaining an O(d3)O(d^3) per-frequency-node dense linear solve. This NuFFT-based class also includes the state-of-the-art implementations against which we benchmark in Sect. 4, namely NIFTY-LS ([12]) and the fast Astropy periodogram implementations ([2]).

In this work, we show that expressing the trigonometric polynomial in its complex exponential form reduces the NuFFT-1-based normal equations to a Hermitian Toeplitz system. This brings the computational cost down to O(dN(log⁡M+log⁡2d))O(dN(\log M+\log^2 d)) operations via superfast Toeplitz solvers, or to O(dN(log⁡M+d))O(dN(\log M+d)) via the Levinson recursion—strictly lower than both previously known fast approaches. Additionally, we discuss the effect of the fast Fourier transform (FFT) block size on empirical execution time and examine the numerical stability of this approximation under condition-number monitoring. Figure 1 illustrates the practical impact of this approach on two representative eclipsing binary light curves from the Optical Gravitational Lensing Experiment (OGLE-IV; [25]), comparing our single-precision implementation (TLSF) against the reference AoVMH implementation (AOVDIST; [30]): both solvers recover the catalog period of OGLE-LMC-ECL-08885, whereas condition-number monitoring in TLSF avoids the daily alias selected by AOVDIST for OGLE-LMC-ECL-15332 at a fraction of the computational cost. Additionally, we examine the effects of matrix conditioning and the parallel scalability of this approach.

Light curves of OGLE-LMC-ECL-08885 and OGLE-LMC-ECL-15332

Figure 1. Light curves of OGLE-LMC-ECL-08885 (left) and OGLE-LMC-ECL-15332 (right) with fitted d=11d = 11 models (dashed curves). The rows show (a) the raw light curves with observation times in HJD − 2 450 000, measured in days (d), and fits folded at the peak periods PP from (b) AOVDIST and (c) TLSF, with zero phase selected at the moment of minimum brightness and single-periodogram computation times given in each phased panel.

Computational complexity of the non-uniform fast Fourier transform

Throughout this paper, we consider the analysis of an unevenly sampled time series consisting of MM observations with observation times tmt_m, measured values ymy_m, and statistical weights wmw_m, for m=1,…,Mm = 1, \ldots, M. The frequency is denoted by ff, with a target grid of NN frequencies, of which BB are evaluated within a single FFT block using frequency step Δf\Delta f.

Additionally, we adopt the type-1 NuFFT formulation ([8]) as named by Greengard & Lee [15], following the application of non-uniform fast Fourier methods to least-squares periodograms pioneered by Press & Rybicki [27]. Under this convention, a NuFFT-1 evaluates sums corresponding to non-uniform measurement times on an equispaced frequency grid

fj=jΔf,j=0,…,B−1.(1)f_j = j \Delta f,\qquad j = 0,\ldots,B-1. \tag*{(1)}

For a block shifted by f0f_0, application of the shift theorem allows us to express the complex Fourier sum Xf0,jX_{f_0,j} evaluated at frequency f0+jΔff_0 + j\Delta f via the NuFFT-1 as

Xf0,j=∑m=1Myme−2πi(f0+jΔf)tm=∑m=1M(yme−2πif0tm)e−2πijΔftm.(2)\begin{aligned} X_{f_0,j} = \sum_{m=1}^{M} y_m e^{-2\pi i(f_0+j\Delta f)t_m} \\ &= \sum_{m=1}^{M} \left(y_m e^{-2\pi i f_0t_m}\right)e^{-2\pi i j\Delta f t_m}. \tag*{(2)} \end{aligned}

Thus, f0f_0 is applied by complex multiplication of the input values, while the internal transform remains type-1, as the frequencies jΔfj\Delta f remain equispaced after the shift operation.

While many different algorithms for evaluating the NuFFT have been proposed, here we follow the convolution-based algorithm developed by Dutt & Rokhlin [8]. However, we note that the optimization procedure described below can be applied to alternative approaches, such as the low-rank approximation-based evaluation (Ruiz-Antolín & Townsend [28]), without requiring any modifications.

Theoretical computational complexity

In the asymptotic regime (N→∞N \to\infty and M→∞M \to\infty) and neglecting constant prefactors, the number of operations required to evaluate the NN frequencies in blocks of size BB is proportional to

Cop(B)=Nlog⁡B+NMB+B,(3)C_{\mathrm{op}}(B) = N\log B + \frac{NM}{B} + B, \tag*{(3)}

where the first term is the FFT operation count, the second term models the repeated frequency shifts of the MM measurements over N/BN/B blocks, and the final term represents the precomputation cost shared by all blocks. Differentiating with respect to BB gives ∂Cop/∂B=N/B−NM/B2+1=(N/B)(1−M/B)+1\partial C_{\mathrm{op}}/\partial B = N/B - NM/B^2 + 1 = (N/B)(1-M/B)+1. In the N/M→∞N/M \to\infty limit, the share of the precomputation per frequency disappears, and the root converges to B0=MB_0 = M. Consequently, the resulting computational complexity of NuFFT-1 becomes

Cop=O(Nlog⁡M).(4)C_{\mathrm{op}} = O(N\log M). \tag*{(4)}

Empirical time complexity

Although the formula for optimizing the operation count is relatively straightforward, in many practical applications other factors (such as memory access patterns) tend to dominate the computational cost. We therefore provide an alternative block-size optimization framework based on the concept of empirical time complexity, as defined by Goldsmith et al. [14]. Under this model, we approximate the FFT time complexity as a power-law function of the transform length and model the wall-clock execution time as

Cemp(B)=NBα+βNMB+γB,α>0, β>0, γ≥0,(5)C_{\mathrm{emp}}(B) = NB^\alpha+ \beta\frac{NM}{B} + \gamma B,\qquad\alpha> 0,\ \beta> 0,\ \gamma\ge0, \tag*{(5)}

where α\alpha, β\beta, and γ\gamma are empirically derived scaling constants. Because the NN frequencies are partitioned into N/BN/B separate transforms, assuming a B1+αB^{1+\alpha} runtime per transform, analogously to the power-law scaling behavior reported by Goldsmith et al. [14], yields (N/B)B1+α=NBα(N/B)B^{1+\alpha} = NB^\alpha for the first term. The second and third terms retain their previous interpretations, with the scaling coefficients accounting for finite sample sizes. Assuming γ=0\gamma= 0 as an initial guess, differentiating with respect to BB yields

Cemp′(B)=αNBα−1−βNMB2,(6)C'_{\mathrm{emp}}(B)=\alpha N B^{\alpha-1}-\beta\frac{NM}{B^2}, \tag*{(6)}

from which the optimal block size is given by

αBα+1=βM,B0=(βMα)1/(1+α).(7)\alpha B^{\alpha+1}=\beta M,\qquad B_0=\left(\frac{\beta M}{\alpha}\right)^{1/(1+\alpha)}. \tag*{(7)}

In finite-sample cases (γ>0\gamma> 0), the positive setup term shifts the root of Cemp′(B)C'_{\mathrm{emp}}(B) to a smaller block size, so Bopt≤B0B_{\mathrm{opt}}\leq B_0. This term is subleading in the asymptotic limit considered here and does not change the scaling. Substituting the optimal block size gives an empirical complexity of

Cemp(B0)=O(NMα/(1+α)).(8)C_{\mathrm{emp}}(B_0)=O\left(NM^{\alpha/(1+\alpha)}\right). \tag*{(8)}

While the optimal block size for the general case (γ>0\gamma> 0) can be determined using numerical optimization algorithms (such as Newton’s method), most of the computationally efficient FFT implementations restrict the number of frequencies per block BB to integers with no prime factors greater than 3. Consequently, direct evaluation of Eq. (5) for suitable candidates below the initial guess B0B_0 remains the most reasonable practical approach. Additionally, we expect CempC_{\mathrm{emp}} to approximate the observed scaling more closely than the operation count CopC_{\mathrm{op}} for most hardware configurations, making the semi-empirical model preferable for practical block-size selection.

Solving systems of linear equations

Although the NuFFT is one of the key components of the multiharmonic least-squares periodogram, it alone is not sufficient to obtain the least-squares solution. Following Palmer [24], fitting the degree-dd trigonometric polynomial at each target frequency ff reduces to solving a system of exactly 2d+12d+1 linear equations, whose computational cost often exceeds the computation required to evaluate the NuFFTs. In this section, we therefore focus on efficient model fitting once the NuFFTs have already been evaluated.

The model used for evaluation can generally be expressed as

ym≈A0+∑k=1d[Akcos⁡(2πkftm)+Bksin⁡(2πkftm)].(9)y_m \approx A_0+\sum_{k=1}^{d}\left[A_k\cos(2\pi k f t_m)+B_k\sin(2\pi k f t_m)\right]. \tag*{(9)}

For conciseness, we introduce the harmonic sums

Ck=∑m=1Mwmcos⁡(2πkftm),Sk=∑m=1Mwmsin⁡(2πkftm),C_k=\sum_{m=1}^{M}w_m\cos(2\pi k f t_m),\qquad S_k=\sum_{m=1}^{M}w_m\sin(2\pi k f t_m),
CkY=∑m=1Mwmymcos⁡(2πkftm),SkY=∑m=1Mwmymsin⁡(2πkftm),C_k^Y=\sum_{m=1}^{M}w_my_m\cos(2\pi k f t_m),\qquad S_k^Y=\sum_{m=1}^{M}w_my_m\sin(2\pi k f t_m),

along with the frequency-independent data sums

Y=∑m=1Mwmym,YY=∑m=1Mwmym2.(10)Y=\sum_{m=1}^{M}w_my_m,\qquad YY=\sum_{m=1}^{M}w_my_m^2. \tag*{(10)}

The zero-frequency term follows the same harmonic sequence, with

C0=∑m=1Mwm,C0Y=Y,C_0=\sum_{m=1}^{M}w_m,\qquad C_0^Y=Y,
S0=0,S0Y=0.S_0=0,\qquad S_0^Y=0.

The degree-dd system is therefore fully determined by the sums CkC_k and SkS_k up to 2d2d, and by CkYC_k^Y and SkYS_k^Y up to dd.

Real basis formulation

By collecting the unknown coefficients into

θ(f)=(A0,…,Ad,B1,…,Bd)T,(11)\theta(f)=(A_0,\ldots,A_d,B_1,\ldots,B_d)^{\mathsf T}, \tag*{(11)}

minimizing the weighted least-squares residual of Eq. (9) reduces to enforcing the zero-gradient condition with respect to θ(f)\theta(f). This produces the system of normal equations [4], which equates the weighted Gram matrix of the trigonometric basis G(f)\mathcal{G}(f) to the data projection vector, namely

G(f)θ(f)=(rc(f)rs(f)),\mathcal{G}(f)\theta(f)=\begin{pmatrix}r^c(f)\\r^s(f)\end{pmatrix},
G(f)=(Gcc(f)Gcs(f)Gsc(f)Gss(f)),\mathcal{G}(f)=\begin{pmatrix}\mathcal{G}^{cc}(f)&\mathcal{G}^{cs}(f)\\\mathcal{G}^{sc}(f)&\mathcal{G}^{ss}(f)\end{pmatrix},

where the right-hand side components are

rpc(f)=CpY,p=0,…,d,r_p^c(f)=C_p^Y,\qquad p=0,\ldots,d,
rqs(f)=SqY,q=1,…,d.r_q^s(f)=S_q^Y,\qquad q=1,\ldots,d.

For p,q∈{0,…,d}p,q\in\{0,\ldots,d\} in the cosine block and p,q∈{1,…,d}p,q\in\{1,\ldots,d\} in the sine block, the matrix entries are given by

Gpqcc(f)=C∣p−q∣+Cp+q2,\mathcal{G}_{pq}^{cc}(f)=\frac{C_{\lvert p-q\rvert}+C_{p+q}}{2},
Gpqss(f)=C∣p−q∣−Cp+q2,\mathcal{G}_{pq}^{ss}(f)=\frac{C_{\lvert p-q\rvert}-C_{p+q}}{2},
Gpqcs(f)=Sp+q+sgn⁡(q−p)S∣q−p∣2,\mathcal{G}_{pq}^{cs}(f)=\frac{S_{p+q}+\operatorname{sgn}(q-p)S_{\lvert q-p\rvert}}{2},
Gsc(f)=Gcs(f)T.\mathcal{G}^{sc}(f)=\mathcal{G}^{cs}(f)^{\mathsf T}.

Since S0=S0Y=0S_0=S_0^Y=0, the q=0q=0 sine equation can be omitted entirely.

Complex Toeplitz formulation

The real-basis formulation above is adequate for low values of dd, but it fails to exploit the symmetry of the system. We therefore change basis to the complex exponential representation of the trigonometric polynomial,

ϕh(t)=e2πihft,h∈{−d,…,d}.(12)\phi_h(t)=e^{2\pi i h f t},\qquad h\in\{-d,\ldots,d\}. \tag*{(12)}

Here we use the conjugated harmonic sums

Ek(f)=Ck−iSk=∑m=1Mwme−2πikftm,(13)E_k(f)=C_k-iS_k=\sum_{m=1}^{M}w_m e^{-2\pi i k f t_m}, \tag*{(13)}
EkY(f)=CkY−iSkY=∑m=1Mwmyme−2πikftm,E_k^Y(f)=C_k^Y-iS_k^Y=\sum_{m=1}^{M}w_my_m e^{-2\pi i k f t_m},

with E−k=Ek‾E_{-k}=\overline{E_k} and E−kY=EkY‾E_{-k}^Y=\overline{E_k^Y}. If x(f)=(x−d,…,xd)Tx(f)=(x_{-d},\ldots,x_d)^{\mathsf T} denotes the coefficient vector in the complex basis, the same least-squares problem becomes

T(f)x(f)=EY(f),(14)\mathcal{T}(f)x(f)=E^Y(f), \tag*{(14)}
Tpq(f)=Ep−q(f),(15)\mathcal{T}_{pq}(f)=E_{p-q}(f), \tag*{(15)}
(EY(f))p=EpY(f),(16)\left(\mathcal{E}^Y(f)\right)_p=E_p^Y(f), \tag*{(16)}

for p,q∈{−d,…,d}p,q\in\{-d,\ldots,d\}. In this representation, the T(f)\mathcal{T}(f) matrix exhibits Hermitian Toeplitz symmetry while remaining mathematically equivalent to the real formulation.

Levinson recursion and conditioning

Several Toeplitz-specific solvers could be applied to this system. While so-called superfast Toeplitz solvers can reach complexities as low as O(dlog⁡2d)O(d\log^2 d) per system, they only become competitive at d≳100d \gtrsim100 [1]. Since most periodogram applications are limited to much lower degrees, we instead focus on the O(d2)O(d^2) Levinson recursion [19], which is typically faster for the relevant problem sizes.

After shifting the harmonic indices by dd, the Toeplitz system has size 2d+12d+1, with shifted right-hand side b(f)=(b0,…,b2d)T\boldsymbol{b}(f)=(b_0,\ldots,b_{2d})^{\mathsf{T}} given by bj≡Ej−dY(f)b_j\equiv E^Y_{j-d}(f) for j=0,…,2dj=0,\ldots,2d. Let a(j)=(a0(j),…,aj(j))T\boldsymbol{a}^{(j)}=(a_0^{(j)},\ldots,a_j^{(j)})^{\mathsf{T}} denote the coefficient vector of the predictor polynomial of order jj, with a0(j)=1a_0^{(j)}=1, and let εj\varepsilon_j be the corresponding prediction error, initialized to ε0=E0=C0\varepsilon_0=E_0=C_0. The Levinson recursion may then be written as

Lj=∑ℓ=0j−1Ej−ℓaℓ(j−1),(17)L_j=\sum_{\ell=0}^{j-1}E_{j-\ell}a_\ell^{(j-1)}, \tag*{(17)}
Kj=−Ljεj−1,(18)K_j=-\frac{L_j}{\varepsilon_{j-1}}, \tag*{(18)}
εj=εj−1(1−∣Kj∣2),(19)\varepsilon_j=\varepsilon_{j-1}(1-\lvert K_j\rvert^2), \tag*{(19)}

for j=1,…,2dj=1,\ldots,2d. The quantities KjK_j are the reflection coefficients, also known as partial correlation coefficients [7]. Given these values, the predictor polynomial can be updated via

aj(j)=Kj,(20)a_j^{(j)}=K_j, \tag*{(20)}
aℓ(j)=aℓ(j−1)+Kjaj−ℓ(j−1)‾,ℓ=1,…,j−1.(21)a_\ell^{(j)}=a_\ell^{(j-1)}+K_j\overline{a_{j-\ell}^{(j-1)}},\qquad\ell=1,\ldots,j-1. \tag*{(21)}

The solution then follows from

mj=bj−∑ℓ=0j−1Ej−ℓxℓ(j−1),qj=mjεj,(22)m_j=b_j-\sum_{\ell=0}^{j-1}E_{j-\ell}x_\ell^{(j-1)},\qquad q_j=\frac{m_j}{\varepsilon_j}, \tag*{(22)}

followed by

xj(j)=qj,(23)x_j^{(j)}=q_j, \tag*{(23)}
xℓ(j)=xℓ(j−1)+qjxj−ℓ(j−1)‾,ℓ=0,…,j−1.(24)x_\ell^{(j)}=x_\ell^{(j-1)}+q_j\overline{x_{j-\ell}^{(j-1)}},\qquad\ell=0,\ldots,j-1. \tag*{(24)}

As derived by Cybenko [5], the condition number of the solved system does not exceed

κ(T)≤κˉ(T)≡(2d+1)⋅∏j=12d1+∣Kj∣1−∣Kj∣.(25)\kappa(\mathcal{T})\le\bar{\kappa}(\mathcal{T})\equiv(2d+1)\cdot\prod_{j=1}^{2d}\frac{1+\lvert K_j\rvert}{1-\lvert K_j\rvert}. \tag*{(25)}

A candidate frequency is rejected as potentially ill-conditioned if κˉ(T)>κmax⁡\bar{\kappa}(\mathcal{T})>\kappa_{\max}, where κmax⁡\kappa_{\max} is a configurable threshold.

Coefficient of determination

Since the real and complex exponential formulations of the fast χ2\chi^2 periodogram are equivalent, the coefficient of determination (also known as the chi-squared ratio) takes an analogous form. In both cases, the reference χ02\chi_0^2 takes the value

χ02=YY−Y2C0.(26)\chi_0^2=YY-\frac{Y^2}{C_0}. \tag*{(26)}

If x(f)\boldsymbol{x}(f) solves T(f)x(f)=EY(f)\mathcal{T}(f)\boldsymbol{x}(f)=\boldsymbol{E}^Y(f), the minimized chi-squared at frequency ff is equal to

χ2(f)=YY−Re⁡[EY(f)∗x(f)].(27)\chi^2(f)=YY-\operatorname{Re}\left[E^Y(f)^*\boldsymbol{x}(f)\right]. \tag*{(27)}

Consequently, the coefficient of determination at a given trial frequency ff can be expressed as

R2(f)=1−χ2(f)χ02=Re⁡[EY(f)∗x(f)]−Y2/C0YY−Y2/C0,(28)R^2(f)=1-\frac{\chi^2(f)}{\chi_0^2}=\frac{\operatorname{Re}\left[E^Y(f)^*\boldsymbol{x}(f)\right]-Y^2/C_0}{YY-Y^2/C_0}, \tag*{(28)}

which is also known as the “standard” normalization of the periodogram.

Moreover, evaluating the coefficients of determination across the frequency search grid requires only the scalar quadratic form Re⁡[EY(f)∗x(f)]=b(f)∗T(f)−1b(f)\operatorname{Re}\left[E^Y(f)^*\boldsymbol{x}(f)\right]=\boldsymbol{b}(f)^*\mathcal{T}(f)^{-1}\boldsymbol{b}(f), rather than the explicit coefficient vector x(f)\boldsymbol{x}(f). In the Levinson recursion, this quantity can be accumulated directly during the forward pass as

Re⁡[EY(f)∗x(f)]=∑j=02d∣ξj∣2εj,(29)\operatorname{Re}\left[E^Y(f)^*\boldsymbol{x}(f)\right]=\sum_{j=0}^{2d}\frac{\lvert\xi_j\rvert^2}{\varepsilon_j}, \tag*{(29)}

where ξ0=b0\xi_0=b_0 and

ξj=∑ℓ=0jaℓ(j)bj−ℓ,j=1,…,2d.(30)\xi_j=\sum_{\ell=0}^{j}a_\ell^{(j)}b_{j-\ell},\qquad j=1,\ldots,2d. \tag*{(30)}

Because the predictor coefficients aℓ(j)a_\ell^{(j)} and prediction errors εj\varepsilon_j are already evaluated during the forward pass of the Levinson recursion, Eq. (29) determines R2(f)R^2(f) without computing the coefficient vector x(f)\boldsymbol{x}(f). Consequently, if the exact values of the fitted harmonic coefficients are not required across the search grid, the solution recurrence given by Eqs. (22)–(24) can be omitted entirely, avoiding the residual evaluations and solution updates at each trial frequency.

Comparison with existing implementations

To directly compare our modified algorithm with currently available open-source software, we implemented the algorithms described in Sects. 2.2 and 3. The implementation relies on the decimation-in-frequency fast Fourier transform [13] and the COBRAVO bit-reversal permutation algorithm [20], using single-, double-, and double-double-precision arithmetic [6]. For the spreading stage, in which the samples are projected onto a uniform grid by convolution with a finite-width kernel, we rely on the zero-th order prolate spheroidal wave function [23], approximated by a modified Remez algorithm [9], and Gauss–Legendre quadrature for deconvolution [3]. We modified our implementations to ignore frequencies at which the upper bound on the condition number, estimated according to Eq. (25), exceeds 5×1055\times10^5 for the single-precision implementation and 101310^{13} for the double-precision implementation, to ensure numerical stability.

Due to the complexity of the described algorithm, we limit ourselves to a high-level description of the implementation. Readers interested in further details can find the code used to obtain the results presented below in the publicly available Toeplitz-LS repository.

Tests on synthetic white noise

To validate the reference implementation, we generated artificial light curves filled with white noise, each containing M=1000M = 1000 measurements. We computed R2R^2 values for grid sizes between N=28N = 2^8 and N=223N = 2^{23} target frequencies in the d=1d = 1 case, which is mathematically equivalent to the generalized Lomb–Scargle periodogram [34]. We used our double-double implementation as the reference and computed average differences over ten runs for our single-precision (TLSF) and double-precision (TLS) implementations. For comparison, we included NIFTY-LS [12], using version 1.1.02 throughout all benchmarks, and ASTROPY-LRA [2], available in Astropy from version 8.03. The full results are shown in Figure 2.

Figure 2. Average absolute R2R^2 error as a function of frequency grid size for degree-one periodograms, as measured for a white noise synthetic light curve containing M=1000M = 1000 measurements.

Our accuracy estimates for NIFTY-LS match those reported by Garrison et al. [12] within a single order of magnitude. We attribute the 12-order-of-magnitude increase in the accuracy of the Astropy package, relative to the values reported for the older ASTROPY-FASPER implementation, to the introduction of the new ASTROPY-LRA implementation based on the low-rank approximation [28]. In contrast, ASTROPY-FASPER relies on time-domain Lagrange polynomial interpolation following Press & Rybicki [27], leading to a significant divergence from the numerically accurate values. Our double-precision implementation exceeds the accuracy of NIFTY-LS and ASTROPY-LRA across the entire frequency grid size range. Additionally, the single-precision implementation retains an average error below 10−810^{-8} for all of the tested grid sizes, making it more than adequate for most practical applications.

In addition to confirming the accuracy of our reference implementation, we measured the performance of all tested methods as a function of the grid length. All measurements were performed on a 16-core AMD Ryzen 9 7945HX CPU; the C code was compiled with version 14.2.0 of the GNU Compiler Collection on a Linux-based operating system with a Python 3.13 runtime. In the synthetic tests, the execution times for both of our implementations scale roughly proportionally to those of NIFTY-LS, with the double-precision implementation at least twice as fast as NIFTY-LS. The single-precision implementation consistently produces shorter runtimes than the double-precision implementation, with a maximum speed-up factor of 4.15×4.15\times at N=223N = 2^{23}. The NIFTY-LS package outperforms ASTROPY-LRA at all tested grid sizes, with a gap exceeding that between our implementations and NIFTY-LS. The full results are shown in Figure 3.

Figure 3. Computation time as a function of frequency grid size for degree-one synthetic benchmarks.

In addition to the d=1d = 1 runs, we measured the average time needed to solve the system of linear equations used by the periodogram at each frequency, for 1≤d≤121 \le d \le12. We compared the Levinson recursion against the Householder QR decomposition provided by the GNU Scientific Library [10] and used in the reference implementation of Palmer [24]. The Levinson recursion achieves a minimum speed-up factor of 15.35×15.35\times at d=6d = 6, with the largest speed-up factors at d=1d = 1 (29.0×29.0\times) and d=12d = 12 (23.7×23.7\times). The full results are shown in Figure 4.

Figure 4. Computation time per system as a function of the degree of the trigonometric polynomial for the Levinson recursion and the GNU Scientific Library Householder QR solver.

Tests on OGLE-IV variable-star photometry

Synthetic data benchmarks provide a useful baseline, but they are not representative of large-scale time-domain sky surveys. There are two key differences that our synthetic tests did not cover. First, observational gaps and visibility windows introduce a risk of ill-conditioning in the normal equations (Garcia-Piquer et al. [11]). Second, multi-core CPU architectures exhibit parallel scaling constraints; total CPU time (measured as cumulative core-hours across all active cores) often increases significantly with the number of worker threads due to memory-bandwidth saturation, as noted by Garrison et al. [12].

To evaluate the performance of our algorithm under realistic observational conditions, we benchmarked our TLSF and TLS implementations against five existing implementations: ASTROPY-LRA and ASTROPY-FASPER, provided as core components of the Astropy library (Astropy Collaboration et al. [2]); AOVDIST4, a reference implementation of the Szegő recursion-based algorithm (Schwarzenberg-Czerny [30]); FASTCHI2 V1.035, a reference implementation of the algorithm published by Palmer [24]; and NIFTY-LS. All observational light curves were obtained by the Optical Gravitational Lensing Experiment (OGLE-IV; Udalski et al. [33]), specifically focusing on two distinct variable-star sub-catalogs from the Large Magellanic Cloud (LMC): pulsating RR Lyrae stars (Soszynski et al. [32]) and eclipsing binary systems (Pawlak et al. [25]).

All benchmarks were evaluated on identical uniform frequency grids for each light curve, starting at fmin⁡=0f_{\min}=0 up to a dataset-specific maximum frequency fmax⁡f_{\max}, with uniform frequency spacing Δf=1/(5dΔt)\Delta f=1/(5d\Delta t), where Δt=max⁡(tm)−min⁡(tm)\Delta t=\max(t_m)-\min(t_m) is the observational time baseline of the light curve and the factor of 5d5d provides five samples per highest-harmonic resolution element 1/(dΔt)1/(d\Delta t). A best-fit frequency was classified as correct if its absolute difference from the catalog frequency did not exceed 1/Δt1/\Delta t. All computations were performed on the 16-core AMD Ryzen 9 7945HX CPU described above, using 15 parallel threads for all tested implementations.

OGLE-IV LMC RR Lyrae

As the first reference dataset, we analyzed 39 931 light curves of OGLE-IV LMC RR Lyrae stars containing at least 50 measurements each (with an average of 492 measurements per light curve). As an external reference, we benchmarked FNPEAKS6, which estimates periods using a weighted Rayleigh Z test (Mardia [22], Sect. 6.2.1b), using a fixed frequency step of Δf=5×10−5 d−1\Delta f=5\times10^{-5}\ \mathrm{d}^{-1} (1-days per day) up to fmax⁡=5 d−1f_{\max}=5\ \mathrm{d}^{-1} and obtaining a recovery rate of 98.20% in 0.098 core-hours7.

For the least-squares implementations, we generated power spectra for each target for both the single-harmonic case (d=1d=1, corresponding to the generalized Lomb–Scargle periodogram) and d=3d=3, representative of a typical degree used for period determination of pulsating variables, evaluated up to fmax⁡=5 d−1f_{\max}=5\ \mathrm{d}^{-1}. The ASTROPY-LRA, AOVDIST, NIFTY-LS, and TLS implementations (along with TLSF at d=1d=1) all returned identical best-fit frequencies across all light curves tested, achieving period recovery rates of 98.91% at d=1d=1 and 96.97% at d=3d=3. In contrast, ASTROPY-FASPER and FASTCHI2 V1.03 returned different periods for a subset of the tested stars in both benchmarks, most likely as a result of their less accurate underlying NuFFT-1 approximations.

Perhaps counterintuitively, at d=3d=3, TLSF returned slightly more best-fit frequencies matching catalog values than the more numerically accurate implementations. In those light curves, the peak frequencies identified by the more precise methods lay in regions where the estimated condition number κˉ\bar{\kappa} exceeded the κmax⁡=5×105\kappa_{\max}=5\times10^{5} limit, which in the case of TLSF likely reduced its susceptibility to aliasing. We discuss these findings in more detail in Sect. 5.

In addition to matching or exceeding the recovery rates of the other tested implementations, TLSF achieved the lowest computational cost in both benchmarks. At d=1d=1, TLSF processed the entire catalog at a total computational cost of 8 core-seconds, corresponding to a throughput of over 75 000 light curves per second and a speed-up of nearly 30×\times over state-of-the-art NIFTY-LS and over 3500×\times over the multithreaded ASTROPY-LRA implementation. At d=3d=3, TLSF executed the benchmark at a total computational cost of 0.087 core-hours, representing a 1600×\times speed-up over ASTROPY-LRA and more than 16×\times over the NIFTY-LS library. The full benchmark results are summarized in Tables 1 and 2.

OGLE-IV LMC eclipsing binaries

In trigonometric least-squares periodograms, the sharper and more complex variability profiles of eclipsing binaries benefit

Notes. Light curves with fewer than 50 measurements were excluded, yielding 39 931 light curves (averaging 492 measurements per curve) evaluated up to fmax⁡=5 d−1f_{\max}=5\ \mathrm{d}^{-1}.

Notes. Light curves with fewer than 50 measurements were excluded, yielding 39 931 light curves (averaging 492 measurements per curve) evaluated up to fmax⁡=5 d−1f_{\max}=5\ \mathrm{d}^{-1}. from a larger number of harmonics to a significantly greater extent than those of pulsating variables. We therefore benchmarked the algorithms across 38 002 OGLE-IV LMC eclipsing binary light curves [25] containing at least 50 measurements (with an average of 509 measurements per light curve), evaluating frequency grids up to fmax⁡=4 d−1f_{\max} = 4\ \mathrm{d}^{-1}. Because the optimal degree of the fitted trigonometric polynomial varies substantially across different datasets, we initialized the search at d=1d = 1 and progressively increased dd until an execution budget of 30 core-hours was exhausted or the algorithm completed the pass at d=12d = 12. Furthermore, due to the uncertainty in detecting secondary eclipses in noisy light curves, we classified a period as successfully recovered if the identified period matched the catalog period, half of it (0.5×), or twice it (2.0×), where the match was assessed in frequency space with the same 1/Δt5\Delta t_5 tolerance. Using the same fixed frequency step of Δf=5×10−5 d−1\Delta f = 5 \times10^{-5}\ \mathrm{d}^{-1}, FNPEAKS achieved a recovery rate of 72.94% in 0.079 core-hours7.

Figure 5 shows the measured computation time as a function of trigonometric-polynomial degree, and Figure 6 illustrates the period recovery rate as a function of computation time (with TLS omitted from both figures for visual clarity). The TLS and TLSF solvers were the only implementations to reach the degree cap of d=12d = 12 within the specified 30 core-hour cumulative computational budget. Furthermore, TLSF was both the least computationally expensive and the most accurate method, achieving the highest period recovery rate of 92.66% at a computational cost of 0.93 core-hours.

Figure 5. Computation time as a function of trigonometric-polynomial degree for the OGLE-IV LMC eclipsing-binary benchmark.

Figure 6. Period recovery rate as a function of computation time for the OGLE-IV LMC eclipsing-binary benchmark.

In addition to the multi-degree sweep, we performed a dedicated benchmark at d=11d = 11 to compare the tested implementations under an equivalent problem formulation. We excluded the Astropy implementations from this comparison due to their prohibitively high computational cost, exceeding 10410^4 core-hours under their expected O(d4)O(d^4) computational complexity within the specified problem formulation. The benchmark results are summarized in Table 3. Unlike the pulsating variable test, recovery rates for eclipsing binaries diverged widely among the implementations as a result of design matrix ill-conditioning for high-degree trigonometric polynomials. In particular, FASTCHI2 V1.03 lacks any condition-number check, accepting unconstrained solutions to ill-conditioned systems and suffering severe numerical degradation, especially when combined with a low-accuracy NuFFT-1 implementation (recovering only 33.86% of periods). Under these conditions, TLSF remained both the most computationally efficient and most accurate of the tested implementations, retaining a speed-up of more than 16× compared to NIFTY-LS.

ImplementationRecovery rate (%)Computation time (core-h)
FASTCHI2 V1.0333.86142.593
AOVDIST90.7026.547
NIFTY-LS84.1216.071
TLS92.561.998
TLSF92.660.928

Table 3. Period recovery rates and computational costs for the OGLE-IV LMC eclipsing binary dataset at d=11d = 11.

We attribute the instability in period determination most likely to the markedly different frequency-rejection strategies of the implementations. Specifically, NIFTY-LS aborted the period search whenever at least one trial frequency was detected as potentially unstable, which occurred for over 10% of the dataset, whereas AOVDIlST rejected only the harmonics determined to be potentially unstable, leaving occasional detections of false periods caused by numerical error propagation.

Discussion

Multiharmonic least-squares periodograms provide an effective method for detecting and characterizing non-sinusoidal periodic variability in unevenly sampled astronomical time series. In large-scale sky surveys, however, the computational cost of evaluating trigonometric polynomials of degree d>1d > 1 often leads pipelines to adopt the single-harmonic case, also known as the generalized Lomb–Scargle periodogram [34]. Classical methods either scale unfavorably with MM (such as the O(dNM)O(dNM) Szegő recursion) or rely on general-purpose linear solvers that incur significant com-

Notes. Light curves with fewer than 50 measurements were excluded, yielding 38 002 light curves (averaging 509 measurements per curve) evaluated up to fmax⁡=4 d−1f_{\max} = 4\ \mathrm{d}^{-1}. putational overhead at higher degrees as a result of their O(d3)O(d^3) scaling.

In this work, we explored whether a multiharmonic trigonometric periodogram can achieve computational throughput and cache efficiency comparable to single-harmonic algorithms without sacrificing period recovery accuracy. By splitting the large-grid NuFFT-1 into multiple cache-resident blocks and solving the resulting complex Hermitian Toeplitz systems via the O(d2)O(d^2) Levinson recursion, both the Fourier evaluation and linear solve stages become substantially more efficient. The overall computational complexity scales as O(dN(log⁡M+d))O(dN(\log M + d)), bringing high-degree evaluations within practical reach.

Our benchmark results confirm the practical advantages of this formulation across synthetic datasets and large observational catalogs. On synthetic white noise (Figure 2–Figure 4), TLS delivers higher accuracy than existing tools while running more than twice as fast as NIFTY-LS for d=1d = 1. The TLSF solver provides an additional speed-up, maintaining average R2R^2 differences below 10−810^{-8} in our benchmarks with M=1000M = 1000 measurements (noting that this error depends on MM). Across tens of thousands of OGLE-IV light curves of pulsating RR Lyrae stars (d=3d = 3, Table 2) and eclipsing binary systems (d=11d = 11, Table 3, Figure 5 and Figure 6), our implementations achieve the highest period recovery rates while reducing execution times by over an order of magnitude compared to previously available implementations.

ImplementationRecovery rate (%)Computation time (core-h)
ASTROPY-LRA96.97144.492
ASTROPY-FASPER95.22138.588
AOVDIST96.975.306
FASTCHI2 V1.0394.805.178
NIFTY-LS96.971.413
TLS96.970.173
TLSF96.980.087

Table 2. Period recovery rates and computational costs for the OGLE-IV LMC RR Lyrae dataset at d=3d=3.

Effects of matrix conditioning on recovery rates

In multiharmonic least-squares fitting, observational cadence gaps and annual visibility windows frequently degrade the conditioning of the normal equations. For d=11d = 11 on the OGLE-IV LMC eclipsing binary dataset, the TLSF and TLS implementations achieve nearly identical period recovery rates for conditioning thresholds κmax⁡≲106\kappa_{\max} \lesssim10^6 (Figure 7). Above that threshold, the recovery rate of TLSF deteriorates as κmax⁡⋅ϵ\kappa_{\max} \cdot\epsilon approaches unity (where ϵ\epsilon denotes the relative numerical accuracy of the underlying NuFFT-1 approximation), whereas TLS remains reliable up to κmax⁡∼1016\kappa_{\max} \sim10^{16}. This precision-dependent instability is illustrated in Figure 8 (right column) for OGLE-LMC-ECL-09937 at κmax⁡=1010\kappa_{\max} = 10^{10}, where TLS recovers the true period (f=0.26559 d−1f = 0.26559\ \mathrm{d}^{-1}) while TLSF fails on a spurious peak (f=2.19925 d−1f = 2.19925\ \mathrm{d}^{-1}) caused by numerical round-off amplification.

Period recovery rate as a function of the conditioning threshold

Figure 7. Period recovery rate of single-precision (TLSF) and double-precision (TLS) implementations as a function of the conditioning threshold κmax⁡\kappa_{\max} for the OGLE-IV LMC eclipsing binary dataset at d=11d = 11.

Light curves of OGLE-LMC-ECL-18477 and OGLE-LMC-ECL-09937 with fitted models

Figure 8. Light curves of OGLE-LMC-ECL-18477 (left) and OGLE-LMC-ECL-09937 (right) with fitted d=11d = 11 models (dashed curves). The rows show (a) the raw light curves with observation times in HJD − 2 450 000, measured in days, (b) mishaped fits, and (c) fits recovering the catalog periods, with zero phase selected at the moment of minimum brightness.

Because both implementations reach their optimal period recovery rate at κmax⁡≲103\kappa_{\max} \lesssim10^3, single precision is expected to be sufficient for most survey pipelines when coupled with a suitable condition-number cutoff. Furthermore, this conditioning behavior is the likely cause of TLSF consistently exceeding the recovery rate of TLS across both the RR Lyrae and eclipsing binary benchmarks (Table 2 and Table 3) by a small margin. The lower rejection threshold in TLSF acts as an effective regularizer, rejecting peaks with weak phase coverage that otherwise mislead unconstrained solvers. Figure 8 (left column) illustrates this regime for OGLE-LMC-ECL-18477: at κmax⁡=1010\kappa_{\max} = 10^{10}, well within the numerically stable range of double precision, TLS locks onto a strong nightly alias (f=2.00282 d−1f = 2.00282\ \mathrm{d}^{-1}), whereas a stricter cutoff of κmax⁡=103\kappa_{\max} = 10^3 rejects the ill-conditioned alias and recovers the true period (f=0.02996 d−1f = 0.02996\ \mathrm{d}^{-1}). We also note that exploring the feasibility of soft regularization of the periodogram test statistic via κ\kappa could potentially reduce the susceptibility of trigonometric periodograms to aliasing.

Numerical error propagation on equispaced frequency grids

In our synthetic benchmarks (Figure 2), the measured average R2R^2 error remains approximately constant across grid sizes up to N=223N = 2^{23}, well below the O(Nϵmach)O(N\epsilon_{\mathrm{mach}}) lower bound on the achievable error proposed by Garrison et al. [12], where ϵmach\epsilon_{\mathrm{mach}} is the upper bound on the relative approximation error due to rounding in the floating-point format used. As shown in Figure 2, neither our implementations nor nifty-ls exhibit the linear O(Nϵmach)O(N\epsilon_{\mathrm{mach}}) error accumulation that Garrison et al. [12] suggested would render single-precision periodograms unusable at large grid sizes. Following the numerical stability analysis of Cybenko [5], we bound the worst-case error accumulation of the Levinson recursion applied to Hermitian Toeplitz systems by O(d2⋅ϵ⋅κmax⁡⋅log⁡N)O(d^2 \cdot\epsilon\cdot\kappa_{\max} \cdot\log N).

Additionally, this upper bound can be lowered to O(κ2⋅ϵ⋅log⁡N)O(\kappa_2 \cdot\epsilon\cdot\log N), with an average accumulated error of O(κ2⋅ϵ⋅log⁡N)O(\kappa_2 \cdot\epsilon\cdot\sqrt{\log N}), if the Levinson recursion is replaced by a more numerically stable linear solver such as the singular value decomposition (Higham [16], Chaps. 20 and 21), where κ2≤κˉ≤κmax⁡\kappa_2 \le\bar{\kappa} \le\kappa_{\max}. Moreover, our empirical tests show that single precision preserves high recovery rates even at degrees as high as d=11d = 11 (Figure 7). Consequently, half-precision implementations may be viable for initial candidate period screening. While our theoretical results show that error accumulation scales favorably as O(log⁡N)O(\sqrt{\log N}) on equispaced grids, determining rigorous lower bounds on both the worst-case error and the average error growth remains an open problem.

Multithreading and scalability

Our benchmarks also reveal a pronounced difference in how multithreading affects the performance of different implementations. In our tests, fastchi2 v1.03 and nifty-ls exhibited strongly sublinear speed-ups with thread count, consistent with the memory-bandwidth bottleneck identified by Garrison et al. [12]. In contrast, our implementations and aovdist achieved near-linear scaling up to the 16 physical cores available on our test platform.

Profiling the different implementations confirms that the near-linear scaling of our method stems from differences in cache locality (Figure 9). Specifically, the block-size optimization described in Sect. 2.2 keeps intermediate FFT results within the core-private L2 cache (yielding an L2 miss rate of 2.5×10−32.5 \times10^{-3} per instruction at the default block size B=211B = 2^{11}), whereas monolithic grid implementations such as nifty-ls exceed cache capacity (5.9×10−35.9 \times10^{-3} misses per instruction) and incur severe DRAM memory-bandwidth contention. Furthermore, we note that, unlike the other implementations, aovdist recomputes the trigonometric functions at every target frequency, which keeps its working set small (2×10−52 \times10^{-5} misses per instruction) at the cost of high arithmetic overhead; on equispaced frequency grids, these evaluations could be replaced by recursive complex multiplications (Ponomarenko (1981); Kurtz [18]), which is likely to substantially accelerate the Szegő recursion and potentially make it competitive for small MM.

Figure 9. L2 data-cache miss rate (defined as the total number of L2 data-cache misses divided by the total number of retired instructions) as a function of FFT block size B=2kB = 2^k for the degree-one periodogram with M=1000M = 1000 measurements and N=220N = 2^{20} frequencies. The vertical dotted line marks the native default block size B=211B = 2^{11}.

Viability of GPU offloading

When evaluated on 15 threads of an AMD Ryzen 9 7945HX CPU, both tls and tlsfit achieve higher throughput than that measured on the NVIDIA A100 GPU by Garrison et al. [12]. While our blocked Toeplitz algorithm is mathematically suited to GPU execution, preliminary benchmarks indicate modest speed-ups over CPU execution. Unless our algorithm is further optimized for GPU offloading, under comparable power and cost constraints, CPUs are likely to exceed the throughput measured on GPUs.

This behavior is most likely driven by the substantial dynamic memory footprint required per thread to maintain intermediate FFT results across thousands of concurrent GPU threads, which limits effective occupancy. Consequently, multicore CPUs with large caches are likely to remain a highly practical and cost-effective hardware platform for multiharmonic period searches.

Implications for large-scale sky surveys

Our benchmarks demonstrate consistent speed-ups exceeding an order of magnitude over existing state-of-the-art tools, enabling high-degree trigonometric polynomial fitting to be deployed routinely across large-scale survey catalogs. This capability makes high-degree harmonic period searches more feasible at the scale of next-generation photometric sky surveys, such as the Vera C. Rubin Observatory Legacy Survey of Space and Time (LSST; Ivezić et al. [17]). Furthermore, as a result of this improved efficiency and numerical stability, high-degree trigonometric periodograms may provide a practical alternative to specialized transit detection algorithms such as the fast-folding box least-squares algorithm (Shahaf et al. [31]).

Conclusions

We present a new implementation of the multiharmonic least-squares periodogram that is more than an order of magnitude faster than the state-of-the-art nifty-ls library (Garrison et al. [12]) across multithreaded benchmarks (Table 1–Table 3; Figure 5). For low to moderate numbers of harmonics (1≤d≤51 \le d \le5), our implementation matches the period recovery rates of nifty-ls on both RR Lyrae (Table 1 and Table 2) and eclipsing binary light curves (Figure 6), while achieving significantly higher recovery rates at the high numbers of harmonics (d>5d > 5) beneficial for sharp eclipsing binary profiles, as ill-conditioned trial frequencies become more common (Figure 6; Table 3).

ImplementationRecovery rate (%)Computation time (core-h)
ASTROPY-LRA98.917.788
ASTROPY-FASPER98.863.437
AOVDIST98.911.051
FASTCHI2 V1.0398.720.310
NIFTY-LS98.910.0650
TLS98.910.0062
TLSF98.910.0022

Table 1. Period recovery rates and computational costs for the OGLE-IV LMC RR Lyrae dataset at d=1d=1.

These performance improvements stem from expressing the system of normal equations as a Hermitian Toeplitz matrix, combining the AoVMH formulation of Schwarzenberg-Czerny [30] with the NuFFT-1 evaluation of the fastchi2 algorithm Palmer [24]. Coupled with the cache-resident blocked NuFFT-1 scheme (Sect. 2.2), this representation enables O(d2)O(d^2) model fitting via the Levinson recursion and allows the coefficient of determination R2(f)R^2(f) to be accumulated directly during the forward pass. Although such a system also admits superfast Toeplitz solvers of O(dlog⁡2d)O(d\log^2 d) complexity, their substantial algorithmic overhead and constant factors cause them to underperform compared to the cache-friendly Levinson recursion for the harmonic degrees (d≤12d \le12) typical of astronomical period searches. Furthermore, excluding individual trial frequencies at which the condition-number upper bound κˉ\bar{\kappa} exceeds the cutoff κmax⁡\kappa_{\max} suppresses numerical instability at high harmonic degrees, with minimal risk of rejecting true variability periods and at negligible additional cost.

Despite these encouraging results, several limitations and open questions remain. First, while the condition-number cutoff κmax⁡\kappa_{\max} reduces susceptibility to aliasing, incorporating κˉ\bar{\kappa} directly into the test statistic as an indicator of phase coverage may prove superior and eliminate the need for an explicit rejection threshold. Second, existing periodogram implementations based on the Szegő recursion do not use recursive complex multiplication to avoid repeated trigonometric evaluations on equispaced frequency grids; determining the empirical crossover point in MM and dd between the Toeplitz formulation and an optimized Szegő recursion would clarify the optimal regime for sparsely sampled light curves. Finally, while direct translation of the Levinson recursion to GPUs is currently constrained by its dynamic memory footprint, evolving accelerator architectures warrant a deeper examination of GPU and heterogeneous implementations. Ultimately, our formulation increases the practical feasibility of high-degree multiharmonic period searches on datasets from large-scale sky surveys, potentially making these searches competitive with domain-specific algorithms not included in our comparison.

Data availability

All performance benchmarks and period recovery rates presented in this paper were derived using the Linux x86-64 build of the v1.1.0 release of the Toeplitz-LS library, which is publicly available along with the benchmark and plotting scripts at https://github.com/kkruttowski/Toeplitz-LS; comparisons against NIFTY-LS used the v1.1.0 source distribution8. The OGLE-IV photometry analyzed in Sect. 4 is publicly available through the OGLE Collection of Variable Stars, with the RR Lyrae stars at https://ogledb.astrouw.edu.pl/~ogle/OCVS/rrlyr_query.php and the eclipsing binaries at https://ogledb.astrouw.edu.pl/~ogle/OCVS/ecl_query.php.

Acknowledgements. This research was funded in part by the National Science Center, Poland, grant Sonata Bis 2021/42/E/ST9/00038 to Radosław Poleski.

Author contributions: KR: Conceptualization, Data Curation, Investigation, Methodology, Software, Validation, Visualization, Formal analysis, Writing – original draft, Writing – review & editing. RP: Conceptualization, Validation, Writing – review & editing, Supervision.

References

  1. [1]Ammar, G. S. & Gragg, W. B. 1988, SIAM J. Matrix Anal. Appl., 9, 61
  2. [2]Astropy Collaboration, Price-Whelan, A. M., Lim, P. L., et al. 2022, ApJ, 935, 167
  3. [3]Barnett, A. H., Magland, J., & Klintenberg, L. 2019, SIAM J. Sci. Comput., 41, C479
  4. [4]Björck, Å. 1996, Numerical Methods for Least Squares Problems (Philadelphia, PA: SIAM)
  5. [5]Cybenko, G. 1980, SIAM J. Sci. Stat. Comput., 1, 303
  6. [6]Dekker, T. J. 1971, Numer. Math., 18, 224–242
  7. [7]Durbin, J. 1960, Rev. Inst. Int. Stat., 28, 233
  8. [8]Dutt, A. & Rokhlin, V. 1993, SIAM J. Sci. Comput., 14, 1368
  9. [9]Fraser, W. 1965, J. ACM, 12, 295–314
  10. [10]Galassi, M., Davies, J., Theiler, J., et al. 2008, GNU Scientific Library Reference Manual (Bristol: Netowrk Theory Ltd.)
  11. [11]Garcia-Piquer, A., Morales, J. C., Ribas, I., et al. 2017, A&A, 604, A87
  12. [12]Garrison, L. H., Foreman-Mackey, D., Shih, Y.-h., & Barnett, A. 2024, Res. Notes AAS, 8, 250
  13. [13]Gentleman, W. M. & Sande, G. 1966, in Proceedings of the November 7-10, 1966, Fall Joint Computer Conference, AFIPS ’66 (Fall) (New York, NY, USA: Association for Computing Machinery), 563–578
  14. [14]Goldsmith, S. F., Aiken, A. S., & Wilkerson, D. S. 2007, in Proceedings of the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering, ESEC-FSE ’07 (New York, NY, USA: Association for Computing Machinery), 395–404
  15. [15]Greengard, L. & Lee, J.-Y. 2004, SIAM Rev., 46, 443
  16. [16]Higham, N. J. 2002, Accuracy and Stability of Numerical Algorithms, 2nd edn. (Philadelphia, PA: SIAM)DOI
  17. [17]Ivezić, Ž., Kahn, S. M., Tyson, J. A., et al. 2019, ApJ, 873, 111
  18. [18]Kurtz, D. W. 1985, MNRAS, 213, 773
  19. [19]Levinson, N. 1946, J. Math. Phys., 25, 261
  20. [20]Lokhmotov, A. & Mycroft, A. 2007, in Proceedings of the Nineteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’07 (New York, NY, USA: Association for Computing Machinery), 198–199
  21. [21]Lomb, N. R. 1976, Ap&SS, 39, 447
  22. [22]Mardia, K. V. 1972, Statistics of Directional Data, Probability and Mathematical Statistics: A Series of Monographs and Textbooks (London: Academic Press), 133–136
  23. [23]Osipov, A., Rokhlin, V., & Xiao, H. 2013, Prolate Spheroidal Wave Functions of Order Zero: Mathematical Tools for Bandlimited Approximation (Springer)DOI
  24. [24]Palmer, D. M. 2009, ApJ, 695, 496
  25. [25]Pawlak, M., Soszyński, I., Udalski, A., et al. 2016, Acta Astron., 66, 421
  26. [27]Press, W. H. & Rybicki, G. B. 1989, ApJ, 338, 277
  27. [28]Ruiz-Antolín, D. & Townsend, A. 2018, SIAM J. Sci. Comput., 40, A529
  28. [29]Scargle, J. D. 1982, ApJ, 263, 835
  29. [30]Schwarzenberg-Czerny, A. 1996, ApJ, 460, L107
  30. [31]Shahaf, S., Zackay, B., Mazeh, T., Faigler, S., & Ivashtenko, O. 2022, MNRAS, 513, 2732
  31. [32]Soszyński, I., Udalski, A., Szymański, M. K., et al. 2016, Acta Astron., 66, 131
  32. [33]Udalski, A., Szymański, M. K., & Szymański, G. 2015, Acta Astron., 65, 1
  33. [34]Zechmeister, M. & Kürster, M. 2009, A&A, 496, 577

Paper details

vlnc:W_sggzg8eu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents