Why is the Fast Fourier Transform efficient?

Question

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.

R Hahn · Accepted Answer · 2011-09-21T05:35:05.263

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 '11 at 05:35

answered Sep 21 '11 at 01:17

R Hahn

2,721

1

@R Hahn your link seems to be broken – Selene Routley Sep 21 '11 at 03:28
It had a forward slash at the end that it shouldn't have. Should be fixed now. – R Hahn Sep 21 '11 at 05:35

Why is the Fast Fourier Transform efficient?

1 Answers1

Linked