Accession Number:

ADA272687

Title:

Fast Fourier Transforms for Nonequispaced Data

Descriptive Note:

Doctoral thesis,

Corporate Author:

YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1993-08-01

Pagination or Media Count:

105.0

Abstract:

Two groups of algorithms are presented generalizing the fast Fourier transform FFT to the case of non-integer frequencies and nonequispaced nodes on the interval -pi, pi. These schemes are based on combinations of certain analytical considerations with the classical fast Fourier transform, and generalize both the forward and backward FFTs. The number of arithmetic operations required by each of the algorithms is proportional to N dot log N N - log1epsilon, where epsilon is the desired precision of computations and N is the number of nodes. Several related algorithms are also presented, each of which utilizes a similar set of techniques from analysis and linear algebra. These include an efficient version of the Fast Multipole Method in one dimension and fast algorithms for the evaluation, integration and differentiation of Lagrange polynomial interpolants. Several numerical examples axe used to illustrate the efficiency of the approach, and to compare the performances of the two sets of nonuniform FFT algorithms. FFT, Trigonometric series, Fourier analysis, Interpolation, Fast multipole method, Approximation theory

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE