FAST FOURIER-TRANSFORMS FOR NONEQUISPACED DATA

A group of algorithms is presented generalizing the fast Fourier trans form to the case of noninteger frequencies and nonequispaced nodes on the interval [-pi, pi]. The schemes of this paper are based on a combi nation of certain analytical considerations with the classical fast Fo urier transform and generalize both the forward and backward FFTs. Eac h of the algorithms requires O(N . log N + N - log(1/epsilon)) arithme tic operations, where epsilon is the precision of computations and N i s the number of nodes. The efficiency of the approach is illustrated b y several numerical examples.