next up previous
Next: Inverse NDFT Up: NDFT Previous: Direct NDFT

Equispaced knots

For $ N_t=N\; (t=0,\hdots,d-1),\; M=N^d$ and equispaced knots $ {x}$$ _{\mbox{\boldmath\scriptsize {${j}$}}}={1 \over N}\mbox{\boldmath {${j}$}} \; (\mbox{\boldmath {${j}$}} \in I_{\mbox{\boldmath\scriptsize {${N}$}}})$ the computation of (2.2) is known as (multivariate) discrete Fourier transform (DFT). In this special case, the input data $ \hat{f}_{\mbox{\boldmath\scriptsize {${k}$}}}$ are called discrete Fourier coefficients and the samples $ f_{\mbox{\boldmath\scriptsize {${j}$}}}$ can be computed by the well known fast Fourier transform (FFT) with only $ {\cal O}\left(N_{\text{\tiny $\Pi$}} \log N_{\text{\tiny $\Pi$}}\right)\; (N_{\text{\tiny $\Pi$}}=N^d)$ arithmetic operations. Furthermore, one has an inversion formula

$\displaystyle \mbox{\boldmath {${A}$}}$   $\displaystyle \mbox{\boldmath {${A}$}}$$\displaystyle ^{\rm H}=$$\displaystyle \mbox{\boldmath {${A}$}}$$\displaystyle ^{\rm H}$   $\displaystyle \mbox{\boldmath {${A}$}}$$\displaystyle = N_{\text{\tiny$\Pi$}} \mbox{\boldmath {${I}$}},$    

which does NOT hold true for the non equispaced case in general.



Stefan Kunis 2004-09-03