next up previous contents
Next: Fast Gaussian gridding Up: Available window functions and Previous: Tensor product based precomputation   Contents

Linear interpolation from a lookup table

For a large number of nodes $ M$ , the amount of memory can by further reduced by the use of lookup table techniques. For a recent example within the framework of gridding see [6]. We suggest to precompute from the even window function the equidistant samples $ \varphi_t(\frac{rm}{Kn_t})$ for $ t=0,\hdots,d-1$ and $ r=0,\hdots,K,\;K\in\ensuremath{\mathbb{N}}$ and then compute for the actual node $ \ensuremath{\boldsymbol{x}}_j$ during the NFFT the values $ \varphi_t((\ensuremath{\boldsymbol{x}}_j)_t - \frac{l_t}{n_t})$ for $ t=0,\hdots,d-1$ and $ l_t\in I_{n_t,m} ((\ensuremath{\boldsymbol{x}}_j)_t)$ by means of the linear interpolation from its two neighbouring precomputed samples.

This method needs only a storage of $ dK$ real numbers in total where $ K$ depends solely on the target accuracy but neither on the number of nodes $ M$ nor on the multidegree $ \ensuremath{\boldsymbol{N}}$ . Choosing $ K$ to be a multiple of $ m$ , we further reduce the computational costs during the interpolation since the distance from $ (\ensuremath{\boldsymbol{x}}_j)_t-
\frac{l_t}{n_t}$ to the two neighbouring interpolation nodes and hence the interpolation weights remain the same for all $ l_t\in I_{n_t,m} ((\ensuremath{\boldsymbol{x}}_j)_t)$ . This method requires $ 2(2m+1)^d$ extra multiplications per node and is used within the NFFT by the flag PRE_LIN_PSI. Error estimates for this approximation are given in [36].


next up previous contents
Next: Fast Gaussian gridding Up: Available window functions and Previous: Tensor product based precomputation   Contents
Jens Keiner 2006-11-20