Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
you mean $O(n\log n)$ –  John Pardon Sep 21 '11 at 0:35

1 Answer 1

up vote 12 down vote accepted

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.

share|improve this answer
1  
@R Hahn your link seems to be broken –  WetSavannaAnimal aka Rod Vance Sep 21 '11 at 3:28
    
It had a forward slash at the end that it shouldn't have. Should be fixed now. –  R Hahn Sep 21 '11 at 5:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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