FAST FOURIER-TRANSFORMS FOR NONEQUISPACED DATA .2.

A group of algorithms generalizing the fast Fourier transform to the c ase of noninteger frequencies and nonequispaced nodes on the interval [-pi, pi] is presented. The schemes of this paper are based on a combi nation of the classical fast Fourier transform with a version of the f ast multipole method, and generalize both the forward and backward FFT s. Each of the algorithms requires O(N . logN + N . log(1/epsilon)) ar ithmetic operations, where epsilon is the precision of computations an d N is the number of nodes; the CPU time requirement of the method is independent of the distribution of the nodes. The efficiency of the sc heme is illustrated by several numerical examples. The approach of thi s paper is compared to the approach taken by Dutt et al. (''Fast Algor ithms for Polynomial Interpolation, Integration, and Differentiation,' ' Tech. Rep. 977, Department of Computer Science, Yale University, 199 3) to the same set of problems. It turns out that the scheme of Dutt e t al, is preferable for the forward problem, while the method introduc ed here is considerably more efficient for the inverse one. (C) 1995 A cademic Press, Inc.