A note on fast Fourier transforms for nonequispaced grids (Q1272511)

We are concerned with fast Fourier transforms for nonequispaced grids. We propose a general efficient method for the fast evaluation of trigonometric polynomials at nonequispaced nodes based on the approximation of the polynomials by special linear combinations of translates of suitable functions \(\varphi\). We derive estimates for the approximation error. In particular, we improve the estimates given by \textit{A. Dutt} and \textit{V. Rokhlin} [SIAM J. Sci. Comput. 14, No. 6, 1368-1393 (1993; Zbl 0791.65108)]. As a practical consequence, we obtain a criterion for the choice of the parameters involved in the fast transforms.