Explaining why FFT is faster than DFT for the general public?

Question

How would you explain why the Fast Fourier Transform is faster than the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?

Answer 1

FFT is an algorithm for computing the DFT. It is faster than the more obvious way of computing the DFT according to the formula.

Trying to explain DFT to the general public is already a stretch. Also, they probably don't know what an algorithm is. Perhaps you could say that there's a fast way of computing the DFT, and that's one more reason why it's so useful.

Answer 2

FFT algorithms are faster ways of doing DFT. It is a family of algorithms and not a single algorithm. How it becomes faster can be explained based on the heart of the algorithm: Divide And Conquer. So rather than working with big size Signals, we divide our signal into smaller ones, and perform DFT of these smaller signals. At the end we add all the smaller DFT to get actual DFT of the big signal. This gives great benefit asymptotically. So for large values of N, we save a lot!! We shall see how much in a while.

Let us try to understand it more with little bit of high school maths:

DFT computation for N point signal takes: N^2 multiplications (this is clear from the basic defintion, you have N points, and for each of the points you have to multiply N complex sinusoids).

Now if we dvivide our N-point signal into two signals S1 and S2 of length N/2, and then perform DFT of these smaller signals, we will be doing (N/2)^2 multiplication for each of the S1 and S2. So total no. of mulitplications performed in calculating DFT of S1 and S2 will be 2 * (N/2)^2. Then to get actual DFT of N point signal we need to add these componets. So we can see that we actually need approximately (see Note below) 2 * (N/2)^2= (n^2)/2 which is half that in case of N point signal.

This reduction of half is a result of dividing the siganls once. But if we continue deviding the signals again and again, we will end up in reducing the amount of computations in each step by an amount which is much lesser than N^2. In fact the over all no. of compuations using this method comes of the order of N*logN.

To get an idea of how fast this is as compared to direct DFT, consider a computer which can execute 1 mulitiplication operation in 1 nano-seconds. Assume that we have a signal having total of N= 10^9 points.

Total number of nanoseconds spent for evaluating DFT by direct method (i.e not using FFT)on the given Computer= N^2= 10 ^ 18 Nano seconds, which is approximately 31 years. While using FFT we shall spent N*logN = (10^9)*log (10^9)= (10^9)*9*log10 = (10^9) * 9 * 3.32 which is approximately equal to 30 * (10^9) or approximately 30secs!!

So using direct DFT you will spend 31 years while using the devide and conquer approach as in FFT you will get the same output only in 3o seconds!! Now its up to you which method will you prefer :-).

The bottom line is that a lot of problem in nature can be solved much easily if they are small in size. The total effort in solving many small sized problems, is often much smaller than in case of solving one big problem; especially, if the size of the problem is very big such as the above example explained.
This is the basic idea on which FFT algorithms are based upon.

Note: I said 'approximately' because it turns out that we cannot add them directly, and indeed we need a mulitplication factor, actually a phase factor, before combining them. But this is still much lesser that no. of multiplicatiosns we need to do in calculating DFT of S1 and S2, so we can neglect this additional multiplication for large values of N.

Dvide and Conquer: an analogy in military

The concept has been used historically in military. For example Sun Tzu (c. 6th century BCE) a Chinese general, military strategist, and author of The Art of War, writes:

It is the rule in war,

1- if ten times the enemy's strength, surround them;

2- if five times, attack them;

3- if double, be able to divide them;

4- if equal,engage them;

5- if fewer, be able to evade them;

6- if weaker, be able to avoid them.

Sun Tzu

FFT works on rule no. 3. Rule 1 and 2 tells that if your computer is very powerful enough, then probably you will not be interested in adopting any 'Dvide and Conquer' approach, becasue the gain in doing so will be very less. Also rule no 4 to 6 tells that when your computer is too weak, forget about conquering the problem, by dividing the problem size. You will have to search some other ways. One such way could be Randomization

Answer 3

What does a Fourier transformation do? It takes a sequence of values, like the sound volume recorded on a CD with 44,100 values per second, and transforms it into frequencies. That is very useful for example for compression, because frequencies change much less than volumes. Or it can be used to remove noise, because when you look at frequencies, noise is much easier to detect. So the Fourier transformation is quite useful. And (surprisingly? Caused by deep mathematics) very luckily Fourier transformation can also be used to transform frequencies back to volumes.

There is a formula for calculating the Fourier transformation. Unfortunately that formula combines every single point with every other point. Just for 1,024 points that’s 1,024 x 1,024 values that need to be combining, which takes over a million operations.

FFT (Fast Fourier transformation) uses some clever tricks to combine 1,000 points with 1,000 points much faster.

First, it combines the first and second point producing two new values, the third and fourth point producing two new points, and so on. Next we split the data into groups of four. It combines the first and third point, and the second and fourth point. Since each of these points already combined two original points, each of the four results combines data from 4 points.

Then the data is split into groups of eight, and FFT combines the 1st and 5th, 2nd and 6th, 3rd and 7th, and 4th and 8th values, and we get 8 results combining 8 values each. We repeat with groups of 16, 32, 64, 128, 256, 512 and 1,024 numbers.

We do a total of 10 rounds, and each round combines 1,024 points with one of 1,024 other points, for a total of 1,024 calculations per round, or 10,240 operations in total, instead of over a million. How all these values are combined has to be done in a really clever way, but once that way was found, FFT is massively more efficient than just following the formula.

Answer 4

For a non maths audience this will be hard, I suggest you keep it as short as possible or omit it entirely but here's my attempt

A DFT is a large matrix that you multiply your input vector by, the naive implementation involves doing n^2 multiplications for an n point DFT (there are a whole bunch of additions too, but at least in hardware the cost of the multiplications will dominate)

An FFT can be seen as transforming the DFT matrix into multiple matrices which when multiplied together give you the same result, crucially some of the terms in the FFT matricies are 0 so all multiplications with these terms can be omitted meaning you end up with fewer multiplications overall.

Answer 5

Calculating one value of X(k) in the frequency domain costs N complex multiplications, so calculating all N of them one by one, "starting over" every time, costs N times N is N^2 complex multiplications.

However, if you first calculate the DFT of all even entries ((N/2)^2 multiplications) and all odd entries (another (N/2)^2 multiplications), for a total of N^2 / 2 multiplications, you can calculate the full DFT from those with just another N/2 multiplications and N additions. For large N that last step can be ignored, and thus you gained a factor of two. If N is a power of two N=2^q, then you can repeat this trick q times by doing it also for the smaller DFTs of the even and odd entries, winning q times a factor 2, thus it becomes N^2 / (2^q) = N^2 / N = N multiplications, but you have to do that q = log2(N) times, so in the asymptotical case you end up with something of the order N log(N).

To see why you can combine the DFTs of even and odd entries in such an easy way, you must realize that you're just summing entries multiplied with evenly spaced complex numbers on the unit circle in the complex plane (Nth roots of 1, which all lay on a circle). So, if you treat the odd entries as the only input for some DFT then you you're only a single rotation away from what you need for the full DFT: the rotation to bring the entries back to where they should be. A rotation means a multiplication, hence N/2 extra multiplications before you can combine the two smaller DFTs with just additions.

Note that the same trick can be applied when N doesn't factor into just 2^q, but when it can be factored into many small prime numbers. For example, if N=p^q you can repeat q times a stage where you calculate p DFT's each of N/p points and then combine those with (p-1)N/p multiplications (rotating p-1 of the DFT's of the previous stage) and (p-1)N additions, for each of the q stages.

Answer 6

Here is an attempt.

The Fourier transform decomposes a signal into superimposed sine waves of various frequencies (this can be demonstrated visually).

It turns out that we can find out the strength of a specific wave in a specific signal by multiplying the signal with the wave and summing the resulting signal (again, this can be demonstrated visually).

---

The fast Fourier transform speeds up this process.

The insight is that if we divide the signal into two equal halves and compute the decomposition of each, then we can use these decompositions to obtain the decomposition of the entire signal (we don't explain how).

Since the two signal involved are smaller, the process is faster (we don't explain why, but we say it in a convincing tone).

We can speed things up further by iterating this process: dividing the original signal into quarters, computing their decomposition, deducing the decomposition of the two halves, and then of the entire signal.

The best performance is obtained by repeating this all the way down: starting with signals containing a single sample, then repeatedly doubling the signal length until we reach the original signal. This is the fast Fourier transform, and it is indeed significantly faster (e.g., xM for signals of length N).

Answer 7

EDIT: Indeed my previous answer was misleading, since I stated that recursive summation like in merge sort saves calculations and that is of course not true.

What does happen here however is that instead of doing 2N operations on each of the N vectors members (multiplication and summation), we do 2*lg(N) operations, which are caused thanks to recycling of 2 of the previous operations each time from our current and from another, different vector member. If you look at the butterfly diagram, you’ll see that we recycle each time: we reuse 2 of the previous calculations. Instead of doing N of them each time. That yields in 2lgN calculations EACH time instead of N.

Answer 8

The FFT exploits a property of the DFT: the DFT of a sequence can be obtained by interleaving the DFTs of the first and second halves of the sequence.

As a DFT on $N$ points takes the evaluation of $N$ sums of $N$ terms ($N^2$ operations), interleaving twice $\dfrac N2$ sums of $\dfrac N2$ terms is less expensive ($\dfrac{N^2}2+N$ operations).

The same trick can of course be reused on the half sequences to further reduce the cost, and so on.

Answer 9

the easiest way to understand why its faster is because FFT uses both cos+sin on the other hand DFT only uses cos, DFT is more common because it requires less space in compression in general for image, sound,... the other comments are do a deep dive, mine is just a taste of the stuff.