Why is the Fast Fourier Transform efficient? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T02:34:21Z http://mathoverflow.net/feeds/question/76013 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76013/why-is-the-fast-fourier-transform-efficient Why is the Fast Fourier Transform efficient? unknown (google) 2011-09-21T00:13:10Z 2011-09-21T05:35:05Z <p>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)\$.</p> <p>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.</p> http://mathoverflow.net/questions/76013/why-is-the-fast-fourier-transform-efficient/76017#76017 Answer by R Hahn for Why is the Fast Fourier Transform efficient? R Hahn 2011-09-21T01:17:57Z 2011-09-21T05:35:05Z <p>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 <a href="http://www.mceliece.caltech.edu/publications/GDL.ps" rel="nofollow">The Generalized Distributive Law</a>.</p>