next up previous contents
Next: No precomputation of the Up: Available window functions and Previous: Linear interpolation from a   Contents

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

$\displaystyle \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.


next up previous contents
Next: No precomputation of the Up: Available window functions and Previous: Linear interpolation from a   Contents
Jens Keiner 2006-11-20