9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ you mean $O(n\log n)$ $\endgroup$ Sep 21, 2011 at 0:35

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ @R Hahn your link seems to be broken $\endgroup$ Sep 21, 2011 at 3:28
  • $\begingroup$ It had a forward slash at the end that it shouldn't have. Should be fixed now. $\endgroup$
    – R Hahn
    Sep 21, 2011 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.