Accession Number:

ADA272648

Title:

Fast Fourier Transforms of Piecewise Constant Functions

Descriptive Note:

Corporate Author:

YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1993-09-01

Pagination or Media Count:

21.0

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 Olog31epsilonN2 log21epsilonN2log 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 Greens 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

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE