Stony Brook Algorithm Repository


Discrete Fourier Transform

Input
Output

Input Description: A sequence of \(n\) real or complex values \(h_i\), \(0 \leq i \leq n-1\), sampled at uniform intervals from a function \(h\).
Problem: The discrete Fourier transform \(H\) of \(h\), \(H_m = \sum_{k=0}^{n-1} h_k e^{2 \pi i k m / n}\), \(0 \leq m \leq n-1\).

Excerpt from The Algorithm Design Manual: Although computer scientists tend to be relatively unfamiliar with Fourier transforms, electrical engineers and signal processors eat them for breakfast. Functionally, Fourier transforms provide a way to convert samples of a standard time-series into the ``frequency domain''. This provides a ``dual'' representation of the function, in which certain operations become easier than in the time domain. Applications of Fourier transforms include:


Implementations

FFTPACK (rating 10)
FFTW (rating 10)
fftw3 (rating 9)
GSL (rating 9)
FFT (rating 7)
Netlib (rating 5)
Moret and Shapiro's Algorithms P to NP (rating 3)


Recommended Books

Algorithms in Java, Third Edition (Parts 1-4) by Robert Sedgewick and Michael Schidlowsky A Primer on Wavelets and Their Scientific Applications by J. Walker The Fourier Transform and its Applications by R. Bracewell
Numerical Recipes in C by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery The Fast Fourier Transform and Its Applications by E. Oran Brigham

Related Problems


Arbitrary-Precision Arithmetic

Simplifying Polygons

Text Compression

Go To Main Page