Fast Fourier Transforms of Piecewise Constant Functions

Abstract

We present an algorithm for the evaluation of the Fourier transform of piecewise constant functions of two variables. The algorithm overcomes the accuracy problems associated with computing the Fourier transform of discontinuous functions; in fact, its time complexity is O(log(3)(1/epsilon)N(2) + log(2)(1/epsilon)(N(2)log N), where epsilon is the accuracy and N is the size of the problem. The algorithm is based on the Lagrange interpolation formula and the Green's theorem, which are used to preprocess the data before applying the Fast Fourier transform. It admits natural generalizations to higher dimensions and to piecewise smooth functions. Fourier transform, Fast algorithms

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1993
Accession Number
ADA272648

Entities

People

  • Eugene Sorets

Organizations

  • Yale University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Blood Coagulation Factors
  • Boundaries
  • Computations
  • Computer Science
  • Discrete Fourier Transforms
  • Equations
  • Error Analysis
  • Errors
  • Fast Fourier Transforms
  • Frequency
  • Integrals
  • Interpolation
  • Intervals
  • Precision
  • Two Dimensional

Readers

  • Approximation Theory.
  • Calculus or Mathematical Analysis