Direct NDFT

The first problem to be adressed can be regarded as a matrix vector multiplication. For a finite number of given Fourier coefficients $\hat f_{\mbox{\boldmath\scriptsize {${k}$}}} \in \mathbb{C}\;(\mbox{\boldmath {${k}$}}\in I_{\mbox{\boldmath\scriptsize {${N}$}}})$ one wants to evaluate the trigonometric polynomial

$$f\left(\mbox{\boldmath {${x}$}}\right) := \sum_{\mbox{\boldmath\s... ...e {i}}} \mbox{\boldmath\scriptsize {${k}$}}\mbox{\boldmath\scriptsize {${x}$}}}$$ (2.1)

at given non equispaced knots ${x}$$_j \in \mathbb{T}^d$. Thus, our concern is the evaluation of

$$f_j = f\left(\mbox{\boldmath {${x}$}}_j\right) := \sum_{\mbox{\bo... ...iptsize {${k}$}}\mbox{\boldmath\scriptsize {${x}$}}_j} \qquad (j=0,\hdots,M-1).$$

In matrix vector notation this reads as

$$\mbox{\boldmath {${f}$}} = \mbox{\boldmath {${A}$}} \mbox{\boldmath {${\hat f}$}}$$ (2.2)

where

$$\mbox{\boldmath {${f}$}} :=\left(f_j\right)_{j=0,\hdots,M-1}, \mbox{\boldmath {${A}$}} :=\left({\rm e}^{-2\pi{\mbox{\scriptsize {i}}} \mbox{\boldmath\sc... ...ht)_{\mbox{\boldmath\scriptsize {${k}$}}\in I_{\mbox{\boldmath\tiny {${N}$}}}}.$$

As already mentioned, all 'vec'-operation are omitted, and the matrix vector product is defined by ${A}$   ${\hat f}$$:={\rm Vec}\left(\mbox{\boldmath {${A}$}}\right) {\rm vec}\left(\mbox{\boldmath {${\hat f}$}}\right)$. The straight forward algorithm of this matrix vector product, which is called ndft, takes ${\cal O}\left(M N_{\text{\tiny $\Pi$}}\right)$ arithmetical operations.

Related matrix vector products are the adjoint ndft

$$\mbox{\boldmath {${\hat f}$}} = \mbox{\boldmath {${A}$}} ^{\rm H} \mbox{\boldmath {${f}$}} , \qquad \hat f_{\mbox{\boldmath\scriptsize {${k}$}}}=\sum_{j=0}^... ...i}}} \mbox{\boldmath\scriptsize {${k}$}}\mbox{\boldmath\scriptsize {${x}$}}_j},$$

the conjugated ndft

$$\mbox{\boldmath {${f}$}} =\overline {\mbox{\boldmath {${A}$}}} \mbox{\boldmath {${\hat f}$... ...i}}} \mbox{\boldmath\scriptsize {${k}$}}\mbox{\boldmath\scriptsize {${x}$}}_j},$$

and the transposed ndft

$$\mbox{\boldmath {${\hat f}$}} = \mbox{\boldmath {${A}$}} ^{\rm T} \mbox{\boldmath {${f}$}} , \qquad \hat f_{\mbox{\boldmath\scriptsize {${k}$}}}=\sum_{j=0}^... ...i}}} \mbox{\boldmath\scriptsize {${k}$}}\mbox{\boldmath\scriptsize {${x}$}}_j},$$

where ${A}$$^{\rm H}=\overline {\mbox{\boldmath {${A}$}}}^{\rm T}$.