NSFFT – nonequispaced sparse FFT
See also the Matlab toolbox.
In order to circumvent the ‘curse of dimensionality’ in multivariate approximation, interpolations on sparse grids were introduced.
Let \(\boldsymbol{N}=(N_1,\ldots,N_d)^{\top}\in 2\mathbb{N}^d\), \(I_{\boldsymbol{N}}^d := \big\{-\frac{N_1}{2},\dots,\frac{N_1}{2}-1\big\}\times \dots\times\big\{-\frac{N_d}{2},\dots,\frac{N_d}{2}-1\big\}\), and \(\mathbb{T}^d := \big[-\frac{1}{2},\frac{1}{2}\big)^d\). The \( d\)-variate \(\mathrm{NFFT}(N_1,\ldots,N_d)\) computes approximations \( \tilde f\) of the trigonometric polynomial \[ f(\boldsymbol{x}) = \sum_{\boldsymbol{k}\in I_{\boldsymbol{N}}^d} \hat f_{\boldsymbol{k}} \; {\rm e}^{ -2 \pi \mathrm{i} \boldsymbol{k} \boldsymbol{x}} \] at arbitrary knots \(\boldsymbol{x}_\ell\in \mathbb{T}^d\), \(\ell=0,\ldots, M-1\).
This library of C functions evaluates the trigonometric polynomial \[ f(\boldsymbol{x}) = \sum_{\boldsymbol{k}\in H_{J}^d} \hat f_{\boldsymbol{k}} \; {\rm e}^{ -2 \pi \mathrm{i} \boldsymbol{k} \boldsymbol{x}} \] at arbitrary knots \(\boldsymbol{x}_\ell\in \mathbb{T}^d\), \(\ell=0,\ldots, M-1\) and for a hyperbolic cross \( H_{J}^d\), which can be partitioned into blocks of indices \(H_{J}^d = \bigcup_{r} (I_{\boldsymbol{N}_r}^d+{\boldsymbol{\rho}}_r)\) with frequency shifts.
Figure: Hyperbolic cross points in 2D
Figure: Hyperbolic cross points in 3D
The algorithms are implemented by Markus Fenn and Stefan Kunis in ./examples/nsfft.