NSFFT - nonequispaced sparse FFT

In order to circumvent the `curse of dimensionality' in multivariate approximation, interpolations on sparse grids were introduced.

Let $\mathit{N}=(N_1,\dots ,N_d{)}^{\mathrm{\top }}\in 2{\mathbb{N}}^d$, $I_{\mathit{N}}^d:=\{-\frac{N_1}{2},\dots ,\frac{N_1}{2}-1\}\times \cdots \times \{-\frac{N_d}{2},\dots ,\frac{N_d}{2}-1\}$, and ${\mathbb{T}}^d:=[-\frac{1}{2},\frac{1}{2}{)}^d$. The $d$-variate $\mathrm{NFFT}(N_1,\dots ,N_d)$ computes approximations $\tilde{f}$ of the trigonometric polynomial $$f(\mathit{x})=\sum _{\mathit{k}\in I_{\mathit{N}}^d}{\hat{f}}_{\mathit{k}}{\mathrm{e}}^{-2\pi \mathrm{i}\mathit{k}\mathit{x}}$$ at arbitrary knots ${\mathit{x}}_{\ell }\in {\mathbb{T}}^d$, $\ell =0,\dots ,M-1$.

This library of C functions evaluates the trigonometric polynomial $$f(\mathit{x})=\sum _{\mathit{k}\in H_J^d}{\hat{f}}_{\mathit{k}}{\mathrm{e}}^{-2\pi \mathrm{i}\mathit{k}\mathit{x}}$$ at arbitrary knots ${\mathit{x}}_{\ell }\in {\mathbb{T}}^d$, $\ell =0,\dots ,M-1$ and for a hyperbolic cross $H_J^d$, which can be partitioned into blocks of indices $H_J^d=\bigcup _r(I_{{\mathit{N}}_r}^d+{\mathit{\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. Related paper are

• Fenn, M., Kunis, S., Potts, D.
  Fast evaluation of trigonometric polynomials from hyperbolic crosses.
  Numer. Algorithms 41, 339-252. (full paper ps, pdf),   2006
   
• D�hler, M., Kunis, S. and Potts, D.
  Nonequispaced hyperbolic cross fast Fourier transform.
  SIAM J. Numer. Anal. 47, 4415 - 4428   (full paper ps, pdf),   2009