Fast Fourier Transforms for Nonequispaced Data

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 - log(1/epsilon), 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

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1993
Accession Number
ADA272687

Entities

People

  • Alok Dutt

Organizations

  • Yale University

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Applied Mathematics
  • Chebyshev Polynomials
  • Complex Numbers
  • Computations
  • Differential Equations
  • Equations
  • Far Field
  • Fast Fourier Transforms
  • Fourier Analysis
  • Fourier Series
  • Numerical Analysis
  • Numerical Integration
  • Real Numbers
  • Sequences
  • Theorems
  • Three Dimensional
  • Two Dimensional

Readers

  • Approximation Theory.
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)