Extend spectraldiff to irregular grids via non-uniform FFT

Motivation

spectraldiff currently requires uniformly sampled data — it uses np.fft internally, which assumes equal spacing. Many real datasets are irregularly sampled (dropped frames, variable-rate sensors, merged data sources), and the other methods that support variable step size (polydiff, splinediff, rbfdiff, rtsdiff, robustdiff) are all in the local/basis-fit family. There is currently no global spectral method that handles irregular grids.

Approach

The Non-Uniform FFT (NUFFT) generalizes the FFT to arbitrary sample locations at near-FFT cost, $O(N \log N)$. The standard spectral differentiation pipeline maps cleanly onto it:

Type 1 NUFFT: scatter irregular samples ${(t_i, x_i)}$ onto a uniform frequency grid $\hat{X}_k$
Multiply by $ik$: spectral derivative operator, same as in the uniform case
Type 2 NUFFT: evaluate the differentiated spectrum back at the original (irregular) sample locations

The recommended backend is finufft (Flatiron Institute), which is actively maintained, pip-installable, and has clean Python bindings:

pip install finufft

Sketch

import numpy as np
import finufft

def spectraldiff_nufft(x, t, high_freq_cutoff=1.0):
    """Spectral differentiation for irregularly-sampled data via NUFFT.

    :param np.array x: signal values at sample locations t
    :param np.array t: sample locations (not necessarily uniform)
    :param float high_freq_cutoff: fraction of Nyquist to retain (0, 1]
    :return: x_hat, dxdt_hat
    """
    N = len(x)
    T = t[-1] - t[0]  # total duration

    # Rescale t to [-pi, pi] as required by finufft
    t_scaled = 2 * np.pi * (t - t[0]) / T - np.pi

    # Type 1: nonuniform -> uniform Fourier coefficients
    X = finufft.nufft1d1(t_scaled, x.astype(complex), N)

    # Wavenumbers
    k = np.fft.fftfreq(N, d=1.0/N)  # integers 0..N/2-1, -N/2..-1

    # High-frequency cutoff (denoising)
    cutoff = int(high_freq_cutoff * N / 2)
    filt = np.ones(N)
    filt[cutoff:-cutoff] = 0

    # Spectral derivative: multiply by ik * (2pi/T)
    omega = 2 * np.pi / T
    X_smooth = filt * X
    X_deriv  = filt * (1j * k * omega) * X

    # Type 2: uniform Fourier coefficients -> values at original (nonuniform) points
    x_hat    = np.real(finufft.nufft1d2(t_scaled, X_smooth)) / N
    dxdt_hat = np.real(finufft.nufft1d2(t_scaled, X_deriv))  / N

    return x_hat, dxdt_hat

Integration notes

The existing spectraldiff signature already accepts dt_or_t; the irregular-grid path would activate when an array is passed, keeping the interface identical.
finufft would be an optional dependency (like cvxpy for tvrdiff/robustdiff), imported lazily with a clear error message if absent.
spectraldiff would gain a checkmark in the Variable step column of Table 1.

Caveats

NUFFT assumes the signal is approximately bandlimited. Heavily non-uniform sampling can alias; the high_freq_cutoff parameter helps but users should be aware.
Edge handling: the current uniform implementation uses even extension to suppress Gibbs-like artifacts; the NUFFT path may need an analogous treatment.

— Claude Sonnet 4.6

After investigation, we've decided not to implement this. finufft requires OpenMP and a full C++ build toolchain, making it a heavy optional dependency that is difficult to install on macOS (Apple's Clang doesn't ship OpenMP; users need to manually install libomp via Homebrew and pass several CMake flags by hand). This friction is incompatible with PyNumDiff's otherwise pure Python/SciPy install experience.

The approach is sound — the three-step pipeline (Type 1 NUFFT → filter → Type 2 NUFFT) with average-dt padding for edge handling works correctly — but the dependency cost isn't worth it. spectraldiff will remain uniform-grid only. Users needing irregular-grid spectral differentiation should look at finufft directly or use one of the variable-step methods already in the package (splinediff, rbfdiff, rtsdiff, robustdiff).

— Claude Sonnet 4.6

Status recheck, Aug 2026

Revisiting this since finufft has moved since the decision above. It now ships prebuilt wheels, so the "requires a full C++ toolchain" claim is no longer true everywhere — but the coverage is incomplete.

finufft 2.5.1 (uploaded 2026-04-08) publishes:

Platform	Wheel?
macOS arm64 (14.0+)	yes
Linux x86_64 (manylinux2014 / manylinux_2_28 / musllinux)	yes
Windows x86_64	yes
macOS x86_64	no
Linux aarch64	no

The wheels are py3-none-*, i.e. the compiled library is bundled and there's no per-CPython build, so where a wheel exists the install is instant and dependency-free.

Where one doesn't, the original failure is unchanged. On an Intel Mac (macOS 15, AppleClang 17, no Homebrew libomp), pip install finufft falls back to a source build and dies at configure time:

CMake Error at .../Modules/FindPackageHandleStandardArgs.cmake:233 (message):
  .../Modules/FindOpenMP.cmake:616 (find_package_handle_standard_args)
  CMakeLists.txt:84 (find_package)
-- Configuring incomplete, errors occurred!
*** CMake configuration failed
ERROR: Failed building wheel for finufft

There is a workaround, which I verified on that same machine:

CMAKE_ARGS="-DFINUFFT_USE_OPENMP=OFF" pip install finufft

This builds cleanly from source with stock AppleClang — no libomp, no hand-passed CMake flags beyond that one — in about three minutes, and nufft1d1 gives correct results afterward. Single-threaded is not a real cost for the 1-D transforms spectraldiff would be doing.

So the situation has improved from "difficult on all Macs" to "difficult on Intel Macs and non-x86 Linux," with a one-line escape hatch for those cases.

I don't think that's enough to reverse the decision yet. A dependency whose install instructions branch on the user's platform can't go in install_requires, and the default pip install finufft still fails outright for some users — which was the actual objection here, not the difficulty per se. spectraldiff stays uniform-grid only for now.

Leaving this closed but flagging it as worth reopening: if finufft ships wheels covering macOS x86_64 and Linux aarch64, the blocking argument goes away and the three-step Type 1 → filter → Type 2 pipeline described above can be revived as-is, since the approach itself was never the problem.

— Claude Opus 5

Update: the upstream gap is narrower than the above implies, and is already fixed in finufft's master — just unreleased.

At the v2.5.1 tag the wheel matrix had Intel macOS commented out (dropped when GitHub retired the macos-13 runner) and no aarch64 Linux entry. Upstream commit 704cbfee (2026-07-01) restored Intel via the macos-15-intel label and added ubuntu-22.04-arm. Their weekly builds have been green since and produce all seven platform artifacts, including macosx_x86_64. I installed the Intel wheel from run 32607119547 on the same machine that fails the source build above, and it works with no toolchain and no libomp (type-1 transform, residual 6.4e-09).

So the wheels exist and are good — there just hasn't been a release since April 2026 to publish them. Filed upstream as flatironinstitute/finufft#909.

That makes the reopen condition here concrete rather than hypothetical: when finufft cuts a release carrying the macOS x86_64 and Linux aarch64 wheels, this issue should be reopened. Watch #909 for that.

— Claude Opus 5

Navigation Menu

Repository navigation

Extend `spectraldiff` to irregular grids via non-uniform FFT #201

Motivation

Approach

Sketch

Integration notes

Caveats

Status recheck, Aug 2026

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Extend spectraldiff to irregular grids via non-uniform FFT #201

Description

Motivation

Approach

Sketch

Integration notes

Caveats

Activity

pavelkomarov commented on Apr 3, 2026

pavelkomarov commented on Aug 27, 2026

Status recheck, Aug 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

Extend `spectraldiff` to irregular grids via non-uniform FFT #201