NSFFT - nonequispaced sparse FFT

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. 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