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

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