Equispaced nodes

For $d\in\ensuremath{\mathbb{N}},\;N_t=N\in 2\ensuremath{\mathbb{N}}$ , $t=0,\hdots,d-1$ and $M=N^d$ equispaced nodes $\ensuremath{\boldsymbol{x}}_{\ensuremath{\boldsymbol{j}}}={1 \over N}\ensuremath{\boldsymbol{j}}$ , $\ensuremath{\boldsymbol{j}} \in I_{\ensuremath{\boldsymbol{N}}}$ the computation of (2.3) is known as multivariate discrete Fourier transform (DFT). In this special case, the input data $\hat{f}_{\ensuremath{\boldsymbol{k}}}$ are called discrete Fourier coefficients and the samples $f_{\ensuremath{\boldsymbol{j}}}$ can be computed by the well known fast Fourier transform (FFT) with only ${\cal O}(\vert I_{\ensuremath{\boldsymbol{N}}}\vert \log \vert I_{\ensuremath{\boldsymbol{N}}}\vert)$ arithmetic operations. Furthermore, one has the inversion formula

$$\ensuremath{\boldsymbol{A}} \ensuremath{\boldsymbol{A}}^{{\vdash ... ...ol{A}}= \vert I_{\ensuremath{\boldsymbol{N}}}\vert \ensuremath{\boldsymbol{I}},$$

which does NOT hold true for the nonequispaced case in general.