NSFFT - nonequispaced sparse FFT
In order to circumvent the `curse of dimensionality' in multivariate
approximation, interpolations on sparse grids
See also the Matlab Toolbox.
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 , and for a hyperbolic cross which can be partitioned into blocks of indices with frequency shifts.
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