Fast discrete convolution in R-2 with radial kernels using non-uniform fast Fourier transform with nonequispaced frequencies

摘要

We introduce a new algorithm for the fast evaluation of discrete convolutions with radial kernels in Double-struck capital R-2 using the non-uniform fast Fourier transform. In contrast with other approaches, a Fourier representation of the kernel is obtained with frequency samples lying on concentric circles rather than on a Cartesian grid. As a consequence, we require much less terms to reach a given accuracy. This allows for a faster evaluation of the discrete convolution at the cost of longer precomputations. We provide a full analysis of the complexity and error of our method. Numerical results are reported.