Fast Polynomial Multiplication using FFT

• Point Value Representation of Polynomial
• Linear time polynomial multiplication in point value form
• Collapsible Set ($n$ $n^{th}$ roots of unity)
• Computing a polynomial in $O(nlogn)$ time on a collapsible set of size $n$
• Converting from point value form to standard polynomial form in $O(nlogn)$ time using the fact that Inverse of the Vandermonde matrix is just a permutation of the rows of the Vandermonde matrix