Using FFT (Fast Fourier Transform) and its inverse to multiply Polynomials

Using FFT (Fast Fourier Transform) and its inverse to multiply Polynomials

The linear time multiplication method for polynomials in point-value form can be used to perform fast and efficient polynomial multiplication in coefficient form by converting a polynomial quickly from coefficient form to point value form(evaluate) and vice versa(interpolate).

Using Fast Fourier Transform (FFT) and its inverse, we can do evaluation and interpolation in time θ (𝑛log𝑛). The product of two polynomials of degree-bound 𝑛 can be computed in time θ (𝑛log𝑛), with both the input and output in coefficient form.

Given the FFT, we have the following θ(nlog n)-time procedure for multiplying two polynomials A(x) and B(x) of degree-bound n, where the input and output representations are in coefficient form. Assume that n is a power of 2; this requirement can be met by adding high-order zero coefficients.

1. Double degree-bound: Create coefficient representations of A(x) and B(x) as degree-bound 2n polynomials by adding ‘n’ high-order zero coefficients to each.
2. Evaluate: Compute point-value representations of A(x) and B(x) of length 2n by applying the FFT of order 2n on each polynomial. These representations contain the values of the two polynomials at the (2n)^th roots of unity.
3. Point wise multiply: Compute a point-value representation for the polynomial C(x) = A(x)B(x) by multiplying these values together point wise. This representation contains the value of C(x) at each (2n)^th root of unity.
4. Interpolate: Create the coefficient representation of the polynomial C(x) by applying the FFT on 2n point-value pairs to compute the inverse DFT.