Fast Gaussian gridding

Two useful properties of the Gaussian window function (2.9) within the present framework were recently reviewed in [29]. Beside its tensor product structure for $d>1$ , which also holds for all other window functions, it is remarkable that the number of evaluations of the form exp() can be greatly decreased. More precisely, for $d=1$ and a fixed node $x_j$ the evaluations of $\varphi(x_j-\frac{l'}{n})$ , $l'\in I_{n,m}(x_j)$ , can be reduced by the splitting

$$\sqrt{\pi b}\varphi\left(x_j-\frac{l'}{n}\right) ={\,\rm {e}}^{-\... ...eft({\,\rm {e}}^{-\frac{2(nx_j-u)}{b}}\right)^l {\,\rm {e}}^{-\frac{l^2}{b}}\,.$$

where $u=\min I_{n,m}(x_j)$ and $l=0,\hdots,2m$ . Note, that the first factor and the exponential within the brackets are constant for each fixed node $x_j$ . Once, we evaluate the second exponential, its $l$ -th power can be computed consecutively by multiplications only. Furthermore, the last exponential is independent of $x_j$ and these $2m+1$ values are computed only once within the NFFT and their amount is negligible. Thus, it is sufficient to store or evaluate $2M$ exponentials for $d=1$ . The case $d>1$ uses $2dM$ storages or evaluations by using the general tensor product structure. This method is employed by the flags FG_PSI and PRE_FG_PSI for the evaluation or storage of $2d$ exponentials per node, respectively.