On the Rapid Evaluation of Trigonometric Series

Abstract : A group of algorithms is presented generalizing the Fast Fourier Transform to the case of non-integer frequencies and non-equispaced nodes on the interval (-pi, pi). The schemes of this paper are based on a combination of certain analytical considerations with the classical Fast Fourier Transform, and generalize both the forward and backward FFTs. Each of the algorithms requires O(N(dot) log N + N(dot) log (1/epsilon)) arithmetic operations, where epsilon is the precision of computations and N is the number of nodes. The efficiency of the approach is illustrated by several numerical examples. (Author)