Fast Fourier Transform: Algorithm Principles and Iterative Implementation
Polynomial Representations A polynomial $A(x) = \sum_{i=0}^{n-1} a_i x^i$ of degree $n-1$ admits two canonical representations. The coefficient representation stores the vector $[a_0, a_1, \ldots, a_{n-1}]$. Alternatively, the point-value representation consists of $n$ distinct evaluation pairs ${(x...