1993/11/01 by A. Dutt, Vladimir Rokhlin · 4 citations
Computer Science · #Digital Filter Design and Implementation #Image and Signal Denoising Methods #Numerical Methods and Algorithms
paper · doi:10.1137/0914081
openalex publication_date 1993/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
A group of algorithms is presented generalizing the fast Fourier transform to the case of noninteger frequencies and nonequispaced nodes on the interval [ - π ,π ]. 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⋅ log N + N⋅ log (1/ε )) arithmetic operations, where ε is the precision of computations and N is the number of nodes. The efficiency of the approach is illustrated by several numerical examples.