Fast Fourier Transforms for Nonequispaced Data II

A group of algorithms is presented generalizing the Fast Fourier Transform to the case of non-integer frequencies and nonequispaced nodes on the interval [-7r, 7r]. The schemes of this paper are based on a combination of the classical Fast Fourier Transform with a version of the Fast Multipole Method, and generalize both the forward and backward FFTs. Each of the algorithms requires O(N- log N + N • log(I/.)) arithmetic operations, where E is the precision of computations and N is the number of nodes. The efficiency of the approach is illustrated by several numerical examples