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.

Improve this question
$\endgroup$
1
  • $\begingroup$ you mean $O(n\log n)$ $\endgroup$
    – John Pardon
    Commented Sep 21, 2011 at 0:35

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ @R Hahn your link seems to be broken $\endgroup$
    – Selene Routley
    Commented 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
    Commented Sep 21, 2011 at 5:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .