WorksPhysics and Astronomy
Faster 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 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 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- trigonometric polynomial (equivalent to fitting a Fourier series truncated at harmonics to a light curve containing measurements) across frequency nodes requires 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 operations by omitting the dense linear solve; however, because the sums are evaluated directly in the time domain, its cost still scales linearly with 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 , sublinear with respect to , at the cost of retaining an 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 operations via superfast Toeplitz solvers, or to 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.

Figure 1. Light curves of OGLE-LMC-ECL-08885 (left) and OGLE-LMC-ECL-15332 (right) with fitted 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 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 observations with observation times , measured values , and statistical weights , for . The frequency is denoted by , with a target grid of frequencies, of which are evaluated within a single FFT block using frequency step .
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
For a block shifted by , application of the shift theorem allows us to express the complex Fourier sum evaluated at frequency via the NuFFT-1 as
Thus, is applied by complex multiplication of the input values, while the internal transform remains type-1, as the frequencies 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 ( and ) and neglecting constant prefactors, the number of operations required to evaluate the frequencies in blocks of size is proportional to
where the first term is the FFT operation count, the second term models the repeated frequency shifts of the measurements over blocks, and the final term represents the precomputation cost shared by all blocks. Differentiating with respect to gives . In the limit, the share of the precomputation per frequency disappears, and the root converges to . Consequently, the resulting computational complexity of NuFFT-1 becomes
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
where , , and are empirically derived scaling constants. Because the frequencies are partitioned into separate transforms, assuming a runtime per transform, analogously to the power-law scaling behavior reported by Goldsmith et al. [14], yields for the first term. The second and third terms retain their previous interpretations, with the scaling coefficients accounting for finite sample sizes. Assuming as an initial guess, differentiating with respect to yields
from which the optimal block size is given by
In finite-sample cases (), the positive setup term shifts the root of to a smaller block size, so . 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
While the optimal block size for the general case () 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 to integers with no prime factors greater than 3. Consequently, direct evaluation of Eq. (5) for suitable candidates below the initial guess remains the most reasonable practical approach. Additionally, we expect to approximate the observed scaling more closely than the operation count 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- trigonometric polynomial at each target frequency reduces to solving a system of exactly 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
For conciseness, we introduce the harmonic sums
along with the frequency-independent data sums
The zero-frequency term follows the same harmonic sequence, with
The degree- system is therefore fully determined by the sums and up to , and by and up to .
Real basis formulation
By collecting the unknown coefficients into
minimizing the weighted least-squares residual of Eq. (9) reduces to enforcing the zero-gradient condition with respect to . This produces the system of normal equations [4], which equates the weighted Gram matrix of the trigonometric basis to the data projection vector, namely
where the right-hand side components are
For in the cosine block and in the sine block, the matrix entries are given by
Since , the sine equation can be omitted entirely.
Complex Toeplitz formulation
The real-basis formulation above is adequate for low values of , but it fails to exploit the symmetry of the system. We therefore change basis to the complex exponential representation of the trigonometric polynomial,
Here we use the conjugated harmonic sums
with and . If denotes the coefficient vector in the complex basis, the same least-squares problem becomes
for . In this representation, the 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 per system, they only become competitive at [1]. Since most periodogram applications are limited to much lower degrees, we instead focus on the Levinson recursion [19], which is typically faster for the relevant problem sizes.
After shifting the harmonic indices by , the Toeplitz system has size , with shifted right-hand side given by for . Let denote the coefficient vector of the predictor polynomial of order , with , and let be the corresponding prediction error, initialized to . The Levinson recursion may then be written as
for . The quantities are the reflection coefficients, also known as partial correlation coefficients [7]. Given these values, the predictor polynomial can be updated via
The solution then follows from
followed by
As derived by Cybenko [5], the condition number of the solved system does not exceed
A candidate frequency is rejected as potentially ill-conditioned if , where is a configurable threshold.
Coefficient of determination
Since the real and complex exponential formulations of the fast periodogram are equivalent, the coefficient of determination (also known as the chi-squared ratio) takes an analogous form. In both cases, the reference takes the value
If solves , the minimized chi-squared at frequency is equal to
Consequently, the coefficient of determination at a given trial frequency can be expressed as
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 , rather than the explicit coefficient vector . In the Levinson recursion, this quantity can be accumulated directly during the forward pass as
where and
Because the predictor coefficients and prediction errors are already evaluated during the forward pass of the Levinson recursion, Eq. (29) determines without computing the coefficient vector . 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 for the single-precision implementation and 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 measurements. We computed values for grid sizes between and target frequencies in the 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 error as a function of frequency grid size for degree-one periodograms, as measured for a white noise synthetic light curve containing 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 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 at . 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 runs, we measured the average time needed to solve the system of linear equations used by the periodogram at each frequency, for . 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 at , with the largest speed-up factors at () and (). 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 up to a dataset-specific maximum frequency , with uniform frequency spacing , where is the observational time baseline of the light curve and the factor of provides five samples per highest-harmonic resolution element . A best-fit frequency was classified as correct if its absolute difference from the catalog frequency did not exceed . 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 (1-days per day) up to 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 (, corresponding to the generalized Lomb–Scargle periodogram) and , representative of a typical degree used for period determination of pulsating variables, evaluated up to . The ASTROPY-LRA, AOVDIST, NIFTY-LS, and TLS implementations (along with TLSF at ) all returned identical best-fit frequencies across all light curves tested, achieving period recovery rates of 98.91% at and 96.97% at . 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 , 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 exceeded the 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 , 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 over state-of-the-art NIFTY-LS and over 3500 over the multithreaded ASTROPY-LRA implementation. At , TLSF executed the benchmark at a total computational cost of 0.087 core-hours, representing a 1600 speed-up over ASTROPY-LRA and more than 16 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 .
Notes. Light curves with fewer than 50 measurements were excluded, yielding 39 931 light curves (averaging 492 measurements per curve) evaluated up to . 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 . Because the optimal degree of the fitted trigonometric polynomial varies substantially across different datasets, we initialized the search at and progressively increased until an execution budget of 30 core-hours was exhausted or the algorithm completed the pass at . 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/ tolerance. Using the same fixed frequency step of , 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 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 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 core-hours under their expected 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.
| Implementation | Recovery rate (%) | Computation time (core-h) |
| FASTCHI2 V1.03 | 33.86 | 142.593 |
| AOVDIST | 90.70 | 26.547 |
| NIFTY-LS | 84.12 | 16.071 |
| TLS | 92.56 | 1.998 |
| TLSF | 92.66 | 0.928 |
Table 3. Period recovery rates and computational costs for the OGLE-IV LMC eclipsing binary dataset at .
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 often leads pipelines to adopt the single-harmonic case, also known as the generalized Lomb–Scargle periodogram [34]. Classical methods either scale unfavorably with (such as the 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 . putational overhead at higher degrees as a result of their 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 Levinson recursion, both the Fourier evaluation and linear solve stages become substantially more efficient. The overall computational complexity scales as , 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 . The TLSF solver provides an additional speed-up, maintaining average differences below in our benchmarks with measurements (noting that this error depends on ). Across tens of thousands of OGLE-IV light curves of pulsating RR Lyrae stars (, Table 2) and eclipsing binary systems (, 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.
| Implementation | Recovery rate (%) | Computation time (core-h) |
| ASTROPY-LRA | 96.97 | 144.492 |
| ASTROPY-FASPER | 95.22 | 138.588 |
| AOVDIST | 96.97 | 5.306 |
| FASTCHI2 V1.03 | 94.80 | 5.178 |
| NIFTY-LS | 96.97 | 1.413 |
| TLS | 96.97 | 0.173 |
| TLSF | 96.98 | 0.087 |
Table 2. Period recovery rates and computational costs for the OGLE-IV LMC RR Lyrae dataset at .
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 on the OGLE-IV LMC eclipsing binary dataset, the TLSF and TLS implementations achieve nearly identical period recovery rates for conditioning thresholds (Figure 7). Above that threshold, the recovery rate of TLSF deteriorates as approaches unity (where denotes the relative numerical accuracy of the underlying NuFFT-1 approximation), whereas TLS remains reliable up to . This precision-dependent instability is illustrated in Figure 8 (right column) for OGLE-LMC-ECL-09937 at , where TLS recovers the true period () while TLSF fails on a spurious peak () caused by numerical round-off amplification.

Figure 7. Period recovery rate of single-precision (TLSF) and double-precision (TLS) implementations as a function of the conditioning threshold for the OGLE-IV LMC eclipsing binary dataset at .

Figure 8. Light curves of OGLE-LMC-ECL-18477 (left) and OGLE-LMC-ECL-09937 (right) with fitted 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 , 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 , well within the numerically stable range of double precision, TLS locks onto a strong nightly alias (), whereas a stricter cutoff of rejects the ill-conditioned alias and recovers the true period (). We also note that exploring the feasibility of soft regularization of the periodogram test statistic via 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 error remains approximately constant across grid sizes up to , well below the lower bound on the achievable error proposed by Garrison et al. [12], where 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 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 .
Additionally, this upper bound can be lowered to , with an average accumulated error of , 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 . Moreover, our empirical tests show that single precision preserves high recovery rates even at degrees as high as (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 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 per instruction at the default block size ), whereas monolithic grid implementations such as nifty-ls exceed cache capacity ( 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 ( 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 .
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 for the degree-one periodogram with measurements and frequencies. The vertical dotted line marks the native default block size .
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 (), 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 () beneficial for sharp eclipsing binary profiles, as ill-conditioned trial frequencies become more common (Figure 6; Table 3).
| Implementation | Recovery rate (%) | Computation time (core-h) |
| ASTROPY-LRA | 98.91 | 7.788 |
| ASTROPY-FASPER | 98.86 | 3.437 |
| AOVDIST | 98.91 | 1.051 |
| FASTCHI2 V1.03 | 98.72 | 0.310 |
| NIFTY-LS | 98.91 | 0.0650 |
| TLS | 98.91 | 0.0062 |
| TLSF | 98.91 | 0.0022 |
Table 1. Period recovery rates and computational costs for the OGLE-IV LMC RR Lyrae dataset at .
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 model fitting via the Levinson recursion and allows the coefficient of determination to be accumulated directly during the forward pass. Although such a system also admits superfast Toeplitz solvers of complexity, their substantial algorithmic overhead and constant factors cause them to underperform compared to the cache-friendly Levinson recursion for the harmonic degrees () typical of astronomical period searches. Furthermore, excluding individual trial frequencies at which the condition-number upper bound exceeds the cutoff 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 reduces susceptibility to aliasing, incorporating 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 and 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]Ammar, G. S. & Gragg, W. B. 1988, SIAM J. Matrix Anal. Appl., 9, 61
- [2]Astropy Collaboration, Price-Whelan, A. M., Lim, P. L., et al. 2022, ApJ, 935, 167
- [3]Barnett, A. H., Magland, J., & Klintenberg, L. 2019, SIAM J. Sci. Comput., 41, C479
- [4]Björck, Å. 1996, Numerical Methods for Least Squares Problems (Philadelphia, PA: SIAM)
- [5]Cybenko, G. 1980, SIAM J. Sci. Stat. Comput., 1, 303
- [6]Dekker, T. J. 1971, Numer. Math., 18, 224–242
- [7]Durbin, J. 1960, Rev. Inst. Int. Stat., 28, 233
- [8]Dutt, A. & Rokhlin, V. 1993, SIAM J. Sci. Comput., 14, 1368
- [9]Fraser, W. 1965, J. ACM, 12, 295–314
- [10]Galassi, M., Davies, J., Theiler, J., et al. 2008, GNU Scientific Library Reference Manual (Bristol: Netowrk Theory Ltd.)
- [11]Garcia-Piquer, A., Morales, J. C., Ribas, I., et al. 2017, A&A, 604, A87
- [12]Garrison, L. H., Foreman-Mackey, D., Shih, Y.-h., & Barnett, A. 2024, Res. Notes AAS, 8, 250
- [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]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]Greengard, L. & Lee, J.-Y. 2004, SIAM Rev., 46, 443
- [16]Higham, N. J. 2002, Accuracy and Stability of Numerical Algorithms, 2nd edn. (Philadelphia, PA: SIAM)DOI
- [17]Ivezić, Ž., Kahn, S. M., Tyson, J. A., et al. 2019, ApJ, 873, 111
- [18]Kurtz, D. W. 1985, MNRAS, 213, 773
- [19]Levinson, N. 1946, J. Math. Phys., 25, 261
- [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]Lomb, N. R. 1976, Ap&SS, 39, 447
- [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]Osipov, A., Rokhlin, V., & Xiao, H. 2013, Prolate Spheroidal Wave Functions of Order Zero: Mathematical Tools for Bandlimited Approximation (Springer)DOI
- [24]Palmer, D. M. 2009, ApJ, 695, 496
- [25]Pawlak, M., Soszyński, I., Udalski, A., et al. 2016, Acta Astron., 66, 421
- [27]Press, W. H. & Rybicki, G. B. 1989, ApJ, 338, 277
- [28]Ruiz-Antolín, D. & Townsend, A. 2018, SIAM J. Sci. Comput., 40, A529
- [29]Scargle, J. D. 1982, ApJ, 263, 835
- [30]Schwarzenberg-Czerny, A. 1996, ApJ, 460, L107
- [31]Shahaf, S., Zackay, B., Mazeh, T., Faigler, S., & Ivashtenko, O. 2022, MNRAS, 513, 2732
- [32]Soszyński, I., Udalski, A., Szymański, M. K., et al. 2016, Acta Astron., 66, 131
- [33]Udalski, A., Szymański, M. K., & Szymański, G. 2015, Acta Astron., 65, 1
- [34]Zechmeister, M. & Kürster, M. 2009, A&A, 496, 577





