NFCT/NFST - nonequispaced fast (co)sine transform

Let nonequispaced nodes $\ensuremath{\boldsymbol{x}}_j \in [0,\frac{1}{2}]^d$ and frequencies $\ensuremath{\boldsymbol{k}}$ in the index sets

$$I_{\ensuremath{\boldsymbol{N}}}^C := \left\{ \ensuremath{\boldsymbol{k}}=\left(k_t\right)_{t=0,\hdots,d-1} \in \ensuremath{\mathbb{Z}}^d: 0 \le k_t < N_t ,\;t=0,\hdots,d-1\right\},$$

$$I_{\ensuremath{\boldsymbol{N}}}^S := \left\{ \ensuremath{\boldsymbol{k}}=\left(k_t\right)_{t=0,\hdots,d-1} \in \ensuremath{\mathbb{Z}}^d: 1 \le k_t < N_t ,\;t=0,\hdots,d-1\right\}$$

be given. For notational convenience let furthermore $\cos(\ensuremath{\boldsymbol{k}} \odot \ensuremath{\boldsymbol{x}}) := \cos(k_0 x_0) \cdot \hdots \cdot \cos(k_{d-1} x_{d-1})$ and $\sin(\ensuremath{\boldsymbol{k}} \odot \ensuremath{\boldsymbol{x}}) := \sin(k_0 x_0) \cdot \hdots \cdot \sin(k_{d-1} x_{d-1})$ .

The nonequispaced discrete cosine and sine transforms are given by

$$f\left(\ensuremath{\boldsymbol{x}}_j\right) = \sum_{\ensuremath{\boldsymbol{k}}\in I_{\ensuremath{\boldsymbol... ...k}}} \cos(2\pi(\ensuremath{\boldsymbol{k}}\odot\ensuremath{\boldsymbol{x}}_j)),$$

$$f\left(\ensuremath{\boldsymbol{x}}_j\right) = \sum_{\ensuremath{\boldsymbol{k}}\in I_{\ensuremath{\boldsymbol... ...k}}} \sin(2\pi(\ensuremath{\boldsymbol{k}}\odot\ensuremath{\boldsymbol{x}}_j)),$$

for $j=0,\hdots,M-1$ and real coefficients $\hat f_{\ensuremath{\boldsymbol{k}}} \in \ensuremath{\mathbb{R}}$ , respectively.

The straight forward algorithm of this matrix vector product, which is called ndct and ndst, takes ${\cal O}(M \vert I_{\ensuremath{\boldsymbol{N}}}^C\vert)$ and ${\cal O}(M \vert I_{\ensuremath{\boldsymbol{N}}}^C\vert)$ arithmetical operations. For these real transforms the adjoint transforms coincide with the ordinary transposed matrix vector products. Our fast approach is based on the NFFT and seems to be easier than the Chebyshev transform based derivation in [44] and faster than the algorithms in [56] which still use FFTs. Instead of FFTs we use fast algorithms for the discrete cosine transform (DCT-I) and for the discrete sine transform (DST-I). For details we refer to [22].