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

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

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