Nonequispaced fast Fourier transform
Hyperbolic cross

# 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