The Fast Fourier Transform computes the DFT quickly. This important algorithm for computer science (not only computer algebra, but also digital signal processing for instance) was (re)-discovered in 1965 by Cooley and Tukey.
Let be a positive even integer, be a primitive -th root of unity and . In order to evaluate at , we follow a divide-and-conquer strategy; more precisely, we consider the divisions with remainder of by and . So let be polynomials such that
(33) |
(34) |
(35) |
(36) |
(37) |
(38) |
(39) |
(40) |
Marc Moreno Maza