Fourier Transform question, math geeks required within

Factual Questions
1

I am currently using a simulation tool that uses DFT rather than the FFT that I learned in differential equations. What is the difference between the two?

Maybe I should say that what I remember of even FFT’s is limited cause dif eq class was over 10 yrs ago.

deb

2

IIRC, DFT means Discreet Fourier Transform

http://astronomy.swin.edu.au/~pbourke/analysis/dft/

Brian

3

Your simulation tool is using Discrete Fourier transforms, which are a way of breaking a continuous function (like an audio waveform) into its frequency spectrum. Given a function f defined over a finite period of time (say from 0 to 2*pi) then the n-th Fourier coefficient
is the value of


int(f(t)*exp(-i*n*t), t=0..2*pi) / (2*pi)

The Discrete Fourier Transform is an algorithm for taking sampled data and determining the Fourier coefficients of the function that was sampled for small values of n, and using those coefficients to express the function as a sum of sines and cosines, which is handy for all sorts of reasons.

This is similar but not the same as the Fourier transform used to help solve differential equations. That Fourier transform turns the function f(t) into the function F(w) defined by


 F(w) = int(f(t)*exp(-i*w*t), t=-infinity..infinity) / sqrt(2*pi)

The differences are the domain of integration (everything, instead of some finite interval) and the fact that w doesn’t have to be an integer like n has to be. Oh, and that square root, which is there for annoying technical reasons.

But just to confuse the issue…I think the acronym “FFT” should stand for “Fast Fourier Transform”, which is a particular implementation of the Discrete Fourier Transform algorithm. In other words, FFT and DFT should refer to the same thing, but neither is what’s used to solve differential equations. Unless there’s another meaning of the acronym “FFT” that I’m not aware of, which is entirely possible (this isn’t my specialty, I only know this because I happen to be studying for my general examination at the moment).

4

Math Geek is spot-on about the difference between DFTs and FFTs. The FFT is a particular method of calculating a DFT that uses a “butterfly” data-movement to take order-n log(n) time to do, rather than the order-n[sup]2[/sup] time for a standard DFT. It’s overhead per iteration is higher, though, so you still see DFTs when you have a small number of samples, such as in JPEG compression, but when you have thousands of samples, the FFT is much faster.

Here’s a cite, albeit in pdf format.

5

Math Geek wow I am in awe of your answer. You have definitely lived up to your name.

thanks
deb

6

When I taught PDE, the only Fourier transform we used was what mathgeek called the discrete one. The other one is called the Fourier integral. They are both used for solving PDEs but at least in the first course, only the discrete one is used. They both turn functions of time into functions of frequency, but the discrete one is for periodic functions and needs only the (discrete) frequencies that fit a whole number of times into the period.

The FFT is simply a very efficient algorithm for computing the DFT.