Editing Bruun's FFT algorithm (section)

== Recursive factorizations and FFTs ==

In order to compute the DFT, we need to evaluate the remainder of <math>x(z)</math> modulo ''N'' degree-1 polynomials as described above. Evaluating these remainders one by one is equivalent to the evaluating the usual DFT formula directly, and requires O(''N''<sup>2</sup>) operations. However, one can ''combine'' these remainders recursively to reduce the cost, using the following trick: if we want to evaluate <math>x(z)</math> modulo two polynomials <math>U(z)</math> and <math>V(z)</math>, we can first take the remainder modulo their product <math>U(z)</math> <math>V(z)</math>, which reduces the [[Degree of a polynomial|degree]] of the polynomial <math>x(z)</math> and makes subsequent modulo operations less computationally expensive.

The product of all of the monomials <math>(z - \omega_N^k)</math> for ''k''=0..''N''-1 is simply <math>z^N-1</math> (whose roots are clearly the ''N'' roots of unity). One then wishes to find a recursive factorization of <math>z^N-1</math> into polynomials of few terms and smaller and smaller degree. To compute the DFT, one takes <math>x(z)</math> modulo each level of this factorization in turn, recursively, until one arrives at the monomials and the final result. If each level of the factorization splits every polynomial into an O(1) (constant-bounded) number of smaller polynomials, each with an O(1) number of nonzero coefficients, then the modulo operations for that level take O(''N'') time; since there will be a logarithmic number of levels, the overall complexity is O (''N'' log ''N'').

More explicitly, suppose for example that <math>z^N-1 = F_1(z) F_2(z) F_3(z)</math>, and that <math>F_k(z) = F_{k,1}(z) F_{k,2}(z)</math>, and so on. The corresponding FFT algorithm would consist of first computing ''x''<sub>''k''</sub>(''z'') = ''x''(''z'') mod
''F''<sub>''k''</sub>(''z''), then computing ''x''<sub>''k'',''j''</sub>(''z'') = ''x''<sub>''k''</sub>(''z'') mod
''F''<sub>''k'',''j''</sub>(''z''), and so on, recursively creating more and more remainder polynomials of smaller and smaller degree until one arrives at the final degree-0 results.

Moreover, as long as the polynomial factors at each stage are [[relatively prime polynomials|relatively prime]] (which for polynomials means that they have no common roots), one can construct a dual algorithm by reversing the process with the [[Chinese remainder theorem]].

===Cooley–Tukey as polynomial factorization===

The standard decimation-in-frequency (DIF) radix-''r'' Cooley–Tukey algorithm corresponds closely to a recursive factorization. For example, radix-2 DIF Cooley–Tukey factors <math>z^N-1</math> into <math>F_1 = (z^{N/2}-1)</math> and <math>F_2 = (z^{N/2}+1)</math>. These modulo operations reduce the degree of <math>x(z)</math> by 2, which corresponds to dividing the problem size by 2. Instead of recursively factorizing <math>F_2</math> directly, though, Cooley–Tukey instead first computes ''x''<sub>2</sub>(''z'' ω<sub>''N''</sub>), shifting all the roots (by a ''twiddle factor'') so that it can apply the recursive factorization of <math>F_1</math> to both subproblems. That is, Cooley–Tukey ensures that all subproblems are also DFTs, whereas this is not generally true for an arbitrary recursive factorization (such as Bruun's, below).