Navigation

Content Hotkeys
Nonequispaced fast Fourier transform
Hyperbolic cross
NNFFT

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 $ \ensuremath{\boldsymbol{N}}=(N_1,\ldots,N_d)^{\top}\in 2\mathbb{N}^d$, $ I_{\ensuremath{\boldsymbol{N}}}^d :=
\big\{-\frac{N_1}{2},\dots,\frac{N_1}{2}-1\big\}\times
\dots\times\big\{-\frac{N_d}{2},\hdots,\frac{N_d}{2}-1\big\}$, and $ \mathbb{T}^d := \big[-\frac{1}{2},\frac{1}{2}\big)^d$. The $ d$-variate NFFT $ (N_1,\ldots,N_d)$ computes approximations $ \tilde f$ of the trigonometric polynomial

$\displaystyle f(\ensuremath{\boldsymbol{x}}) = \sum_{\ensuremath{\boldsymbol{k}...
...box{\rm\scriptsize {i}}\ensuremath{\boldsymbol{k}} \ensuremath{\boldsymbol{x}}}$

at arbitrary knots $ \ensuremath{\boldsymbol{x}}_\ell\in \mathbb{T}^d$, $ \ell=0,\ldots, M-1$.

This library of C functions evaluates the trigonometric polynomial

$\displaystyle f(\ensuremath{\boldsymbol{x}}) = \sum_{\ensuremath{\boldsymbol{k}...
...box{\rm\scriptsize {i}}\ensuremath{\boldsymbol{k}} \ensuremath{\boldsymbol{x}}}$

at arbitrary knots $ \ensuremath{\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_{\mbox{\boldmath\scriptsize {${N}$}}_r}^d+\ensuremath{\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

oFenn, M., Kunis, S., Potts, D.
Fast evaluation of trigonometric polynomials from hyperbolic crosses.
Numer. Algorithms 41, 339-252. (full paper ps, pdf),   2006

oDö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