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
,
,
and
.
The
-variate NFFT
computes
approximations
of the trigonometric polynomial
at arbitrary knots


This library of C functions evaluates the trigonometric polynomial
at arbitrary knots




The algorithms are implemented by Markus Fenn and Stefan Kunis in ./examples/nsfft. Related paper are

Fast evaluation of trigonometric polynomials from hyperbolic crosses.
Numer. Algorithms 41, 339-252. (full paper ps, pdf), 2006

Nonequispaced hyperbolic cross fast Fourier transform.
SIAM J. Numer. Anal. 47, 4415 - 4428 (full paper ps, pdf), 2009