PARAMETER SELECTION AND ACCURACY IN TYPE-3 NON-UNIFORM FFTS BASED ON GAUSSIAN GRIDDING

We provide a su cient condition to select the parameters of Type 3 Non-Uniform Fast Fourier Transform (NUFFT) algorithms based on the Gaussian gridding to ful ll a prescribed accuracy. This is a problem of signi cant interest in many areas of applied electromagnetics, as for example fast antenna analysis and synthesis and fast calculation of the scattered elds, as well as in medical imaging comprising ultrasound tomography, computed axial tomography, positron emission tomogr aphy and magnetic resonance imaging. The approach is related to the one dimensional case and follows the work in A. Dutt and V. Rokhlin, SIAM J. Sci. Comp. 14 (1993). The accuracy of the proposed choice is rst numerically assessed and then compared to that achieved by the approach in J.-Y. Lee and L. Greengard, J. Comp. Phys. 206 (2005). The convenience of the strategy devised in this paper is shown. Finally, the use of the Type 3 NUFFT is highlighted for an electromagnetic application consisting of the implementation of the aggregation and disaggregation steps in the fast calculation of the scattered eld by the Fast Multipole Method.