next up previous contents
Next: The ansatz Up: Notation, the NDFT, and Previous: Equispaced nodes   Contents

NFFT - nonequispaced fast Fourier transform

For the sake of simplicity, we explain the ideas behind the NFFT for the one-dimensional case $ d=1$ and the algorithm NFFT. The generalisation of the FFT is an approximative algorithm and has computational complexity $ {\cal O}\left(N \log N + \log
\left(1/\varepsilon\right) M\right)$ , where $ \varepsilon$ denotes the desired accuracy. The main idea is to use standard FFTs and a window function $ \varphi $ which is well localised in the time/spatial domain $ \mathbb{R}$ and in the frequency domain $ \mathbb{R}$ . Several window functions were proposed in [15,7,55,25,24].

The considered problem is the fast evaluation of

$\displaystyle f\left(x\right) = \sum_{k\in I_N} \hat{f}_k {\rm e}^{-2\pi{\mbox{\scriptsize {i}}} k x}$ (2.4)

at arbitrary nodes $ x_j \in \ensuremath{\mathbb{T}},\;j=0,\hdots,M-1$ .



Subsections

Jens Keiner 2006-11-20