Non-equispaced fast Fourier transforms with applications to tomography

In this article we describe a non-equispaced fast Fourier transform. It is similar to the algorithms of Dutt and Rokhlin [4] and Beylkin [2] but is based on an exact Fourier series representation. This results in a greatly simplified analysis and increased flexibility. The latter can be used to achieve more efficiency. Accuracy and efficiency of the resulting algorithm are illustrated by numerical examples. In the second part of the article the non-equispaced FFT is applied to the reconstruction problem in Computerized Tomography. This results in a different view of the gridding method of O'Sullivan [9] and in a new ultra fast reconstruction algorithm. The new reconstruction algorithm outperforms the filtered backprojection by a speedup factor of up to 100 on standard hardware while still producing excellent reconstruction quality.