nufftcf

Fast autocorrelation (ACF) and cross-correlation (CCF) function estimation for irregularly- and regularly-sampled time series, thanks notably to the Nonuniform Fast Fourier Transform library developped by the Flatiron Institut (FINUFFT).

nufftcf Fourier-based methods are much faster than the O(\(n^2\)) complexity of direct methods. See benchmark/ for measured scaling of each estimator family -- the tables below give a rough guide only.

See CHANGELOG.md for release notes.

With nufftcf three estimator families are provided for the ACF:

Function	Sampling	Method	Scaling	Notes
compute_acf_gaussian_nufft	irregular	NUFFT + Wiener-Khinchin	\(\sim~O(nK)\)	fastest for long series with many lags(i.e. \(K\gtrsim\) hundreds); ~1-3% residual amplitude bias on strongly periodic signals (see below)
compute_acf_rectangle_nufft	irregular	NUFFT + Wiener-Khinchin	\(\sim~O(nK)\)	same caveat as above
compute_acf_gaussian_realspace	irregular or regular	direct real-space weighted sum	\(O(nK)\)	artifact-free reference; faster than _nufft for a handful of lags (see below)
compute_acf_rectangle_realspace	irregular or regular	direct real-space weighted sum	\(O(nK)\)	artifact-free reference; faster than _nufft for a handful of lags (see below)
compute_acf_regular_fft	regular only	classic FFT correlation, no kernel	\(\sim~O(n)\)	matches Pastas bin_method="regular" to numerical precision
compute_acf_rectangle_fft	regular only	classic FFT correlation + box filter	\(\sim~O(n\log n)\), independent of \(K\)	faster than _nufft/_realspace on regular data (no NUFFT/numba overhead)
compute_acf_gaussian_fft	regular only	classic FFT correlation + gaussian filter	\(\sim~O(n\log n)\), independent of \(K\)	same

\(K\) is the number of requested lags. All seven ACF functions share the same calling convention: fn(lags, t, x, bin_width=0.5) (compute_acf_regular_fft has no bin_width, since it applies no smoothing kernel), and return (c, b) -- the ACF estimate and the effective pair count, both shape (len(lags),).

Cross-correlation functions (CCF)

The same NUFFT + Wiener-Khinchin and real-space machinery is also available for the cross-correlation function between two irregularly-sampled series (t, x) and (s, y), which may have different lengths and different sampling times:

Function	Sampling	Method	Scaling	Notes
compute_ccf_gaussian_nufft	irregular	NUFFT + Wiener-Khinchin	\(\sim~O(nK)\)	fastest for long series with many lags (i.e. \(K\gtrsim\) hundreds); same residual-bias caveat as the ACF _nufft variants
compute_ccf_rectangle_nufft	irregular	NUFFT + Wiener-Khinchin	\(\sim~O(nK)\)	same caveat as above
compute_ccf_gaussian_realspace	irregular or regular	direct real-space weighted sum	\(O(nK)\)	artifact-free reference; faster than _nufft for a handful of lags (see below)
compute_ccf_rectangle_realspace	irregular or regular	direct real-space weighted sum	\(O(nK)\)	artifact-free reference; faster than _nufft for a handful of lags (see below)
compute_ccf_rectangle_fft	regular, same dt/lattice only	classic FFT cross-correlation + box filter	\(\sim~O(n\log n)\), independent of \(K\)	faster than _nufft/_realspace when both series share a sampling grid (no NUFFT/numba overhead)
compute_ccf_gaussian_fft	regular, same dt/lattice only	classic FFT cross-correlation + gaussian filter	\(\sim~O(n\log n)\), independent of \(K\)	same

\(K\) is the number of requested lags. All six share the calling convention fn(lags, t, x, s, y, bin_width=0.5) and return (c, b) -- the CCF estimate (Pearson-normalised, c ~ 1 at perfect correlation) and the effective pair count, both shape (len(lags),). By convention, a positive lag means y lags behind x (i.e. the CCF peaks at lag = tau0 when y(t) ~ x(t - tau0)).

compute_ccf_rectangle_fft / compute_ccf_gaussian_fft (in fft_ccf.py) are the CCF counterparts of compute_acf_rectangle_fft / compute_acf_gaussian_fft: they require t and s to each be regularly spaced with the same sampling step, and to lie on a common integer sampling lattice (s[0] - t[0] a multiple of dt) -- raising ValueError otherwise, in which case use the nufft or realspace estimators instead. There is no _regular (no-kernel) CCF variant, since none exists for the nufft/realspace families either.

Important: t and s must be expressed on a common time origin (e.g. elapsed days since the same reference date for both series). t_numeric_of alone uses each series' own first sample as origin, which is not suitable for two independently-sampled series -- using it separately on x and y would silently misalign the lags. Build t/s from a shared reference date instead (see the example below).

Practical takeaways

• For any n, both nufftcf families (_nufft and _realspace) vastly outperform Pastas quadratic bin methods and pyZDCF -- e.g. at n=256,000, Pastas takes ~55 min against ~10-20 s for nufftcf (benchmark/, ~2 orders of magnitude against pyZDCF too, see notebook/zdcf_vs_nufftcf.ipynb). This holds regardless of K (number of requested lags), so it is encouraged to use nufftcf.
• Between _nufft and _realspace themselves, the faster one is set by K, not n (the crossover barely moves with n, see the estimator guide): _nufft wins once K exceeds a kernel-dependent threshold \(K^*\), empirically ~60-70 for the Gaussian kernel, ~300-400 for rectangle. Below \(K^*\), _realspace is competitive or faster; typical usage (seasonal/annual lag grids, tens to hundreds of lags) is usually well above it.
• Rehfeld et al. (2011) find the Gaussian kernel to be "a reliable and more robust estimator" than other kernels for irregularly-sampled correlation analysis -- and it conveniently also has the lower \(K^*\), so _nufft functions may be prefered.