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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1992
Accession Number
ADA249029

Entities

People

  • A. Dutt
  • Vladimir Rokhlin

Organizations

  • Yale University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Arithmetic
  • Coefficients
  • Complex Numbers
  • Computations
  • Differential Equations
  • Digital Computers
  • Discrete Fourier Transforms
  • Equations
  • Fast Fourier Transforms
  • Fourier Analysis
  • Fourier Series
  • Inequalities
  • Numbers
  • Precision
  • Real Numbers

Readers

  • Calculus or Mathematical Analysis
  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.