Welcome to MathOverflow

Question

8

2

Is there a conceptual way to understand where the Fast Fourier Transform is avoiding redundant computation and thus achieving $O(n\log n)$ instead of $O(n^2)$.

Consider a standard example of the FFT to multiply two polynomials faster. Its not obvious to me conceptually why the FFT should yield a faster way to multiply two polynomials.

edited Sep 21 2011 at 0:58

asked Sep 21 2011 at 0:13

unknown (google)
445●1●7

you mean $O(n\log n)$ – unknown (google) Sep 21 2011 at 0:35

R Hahn · Accepted Answer · 2011-09-21 05:35:05Z UTC

12

Conceptually the FFT takes advantage of a shortcut similar to the distributive law for multiplication. To compute $$(x_1 + x_2)(x_3 + x_4)$$ on could either add first (twice) and then multiply (once), or one could expand $$sx_1x_3 + x_1x_4 + x_2x_3 + x_2x_4$$ and multiply (four times) and then add (three times). This idea has been spelled out in the paper The Generalized Distributive Law.

edited Sep 21 2011 at 5:35

answered Sep 21 2011 at 1:17

R Hahn
1,323●1●6●10

1

@R Hahn your link seems to be broken – WetSavannaAnimal aka Rod Vance Sep 21 2011 at 3:28

It had a forward slash at the end that it shouldn't have. Should be fixed now. – R Hahn Sep 21 2011 at 5:35

Why is the Fast Fourier Transform efficient?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.