In Computer Algebra we use the discrete Fast Fourier Transform to multiply two polynomials a(x) and b(x) in ℤp[x] for a prime p of the form p = 2nq+1 with 2n > deg a + deg b. These primes are called Fourier primes. For example p = 3·230+1. Combined with the Chinese remainder theorem, we get fast multiplication algorithms for ℤ and ℤ[x].
Michael Monagan, Simon Fraser University (2 lectures, 4 hours)
Lecture 1 : Roots of unity, the Fast Fourier Transform. Cost of the FFT, fast polynomial multiplication.
Video Lec10Anotes.pdf Lec10Bnotes.pdf Lec10Cnotes.pdf Lec10Handouts.zipLecture 2 : Fast integer multiplication using the FFT. Tutorial.
Video Lec13Anotes.pdf Lec13Cnotes.pdf Lec13Handouts.zip
The following lectures were given subsequently in my Topics in Computer Algebra course. The first half of Lecture 3 reviews the FFT algorithm from Lecture 1 (see Ch. 4 of [1]) and how to use it to multiply polynomials in O(n log n). The second half presents a second FFT algorithm from (see Ch. 8 of [2]), analyses the FFT permutation in both FFT algorithms and shows how to eliminate the permutations from the forward and inverse transforms when multiplying polynomials using the FFT. Lecture 4 presents two fast algorithms (see [2]) built on top of fast polynomial multiplication.
Lecture 3A : The FFT and fast polynomial multiplication. Video
Lecture 3B : Another FFT algorithm. Removing the FFT permutation. VideoLecture 4A : Fast polynomial division. Video
Lecture 4B : Fast multipoint evaluation. Video
[1] Geddes, Labahn and Czapor, Algorithms for Computer Algebra, Kluwer, 1992.
[2] von zur Gathen and Gerhard, Modern Computer Algebra, Cambridge, 2003.