Jump to main content
Nonequispaced fast Fourier transform
Hyperbolic cross

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
\includegraphics[scale=0.6]{nsfft/sparse2D_0.eps} \includegraphics[scale=0.6]{nsfft/sparse2D_1.eps} \includegraphics[scale=0.6]{nsfft/sparse2D_2.eps} \includegraphics[scale=0.6]{nsfft/sparse2D_3.eps}




Figure: Hyperbolic cross points in 3D
\includegraphics[scale=0.6]{nsfft/sparse3D_0.eps} \includegraphics[scale=0.6]{nsfft/sparse3D_1.eps} \includegraphics[scale=0.6]{nsfft/sparse3D_2.eps} \includegraphics[scale=0.6]{nsfft/sparse3D_3.eps}


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