Saturday, 29 November 2014

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