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].