Polynomial

• Let \(P(x) = p_0 + p_1x + p_2x^2 + \dots + p_dx^d\)

Coefficients representations

• \(P(x): [p_0, p_1,\dots,p_d]\)

Value representations

• Any polynomial of degree \(d\) can be uniquely represented by \(d+1\) points.
• \(\{(x_0, P(x_0)),(x_1, P(x_1)),\dots, (x_d, P(x_d))\}\).
• Examples:
  • Two points, there is exactly one line that goes through these two points.
  • Three points, there is exactly one quadratic function that goes through all there of these points.
  • Four points, there is exactly one cubic function that goes through all these points.

Evaluation

• Mean: coefficients representations => value representations
• \(P(x) = p_0 + p_1x + p_2x^2 + \dots + p_dx^d\)
• Evaluate at \(n \geqslant d +1\) points.
• I pick \(1, 2,\dots , n\) as \(n\) points. So we have:

• Each evaluation will take \(O(d)\) operations, then all evaluations take \(O(nd)\) which ends up being \(o(d^2)\) to evaluate all \(n\) points.

• Question: Can we find a way to optimize this?

• Instead of considering \(P(x)\), we wanted to instead just evaluate a simple polynomials like \(p(x) = x^2\) and \(p(x) = x^3\) and evaluate at 8 points.

• Which points we should pick?

• Is there any set of points when knowing value of one point immediately implies the value of another?

• In fact there is:

  • If we pick \(x=1\) we immediately know the value of the point \(x=-1\). Similarly:
  \[\begin{aligned} (1, 1) \space\space&\text{immediately know the value} \space\space (-1, 1)\\ (2, 4) \space\space&\text{immediately know the value} \space\space (-2, 4)\\ (3, 9) \space\space&\text{immediately know the value} \space\space (-3, 9)\\ (4, 16) \space\space&\text{immediately know the value} \space\space (-4, 16) \end{aligned} \]
  • Extending this idea the key property we want here is that our eight points should be positive and negative pairs
  • The reason this works is due to property of even functions where a function evaluated a \(-x\) is going to equal the function evaluated at positive \(x\)
  • So \(P(-x) = P(x)\).
  • What about \(P(x) = x^3\)? Dose the same trick work?
  • It actually kind of does but one caveat. Each positive \(x\) value will have the same value as negative \(x\) value but with sign flipped
  \[\begin{aligned} (1, 1) \space\space&\text{immediately know the value} \space\space (-1, -1)\\ (2, 8) \space\space&\text{immediately know the value} \space\space (-2, -8)\\ (3, 27) \space\space&\text{immediately know the value} \space\space (-3, -27)\\ (4, 64) \space\space&\text{immediately know the value} \space\space (-4, -64) \end{aligned} \]
  • So, \(P(-x) = -P(x)\).

• So, in these two cases of odd and even degree single term polynomials instead of evaluating 8 individual points we can actually get away with evaluating exactly 4 positive points, which we immediately know the value of the respective negative points

• More general example:

  • \(P(x) = 3x^5 + 2x^4 + x^3 + 7x^2+ 5x + 1\).
  • Evaluate at \(n\) points \(\pm x_1, \pm x_2,\dots, \pm x_{\frac{n}{2}}\).
  • Split polynomial into even and odd degree terms:
    • \(P(x) = (2x^4 + 7x^2 + 1) + (3x^5 + x^3 + 5x)\).
  • Factor an \(x\) from the odd degree terms:
    • \(P(x) = (2x^4 + 7x^2 + 1) + x(3x^4 + x^2 + 5)\).
  • We have two new polynomials have only even degree terms: \(P_e(x^2), P_o(x^2)\).
  • \(P(x) = P_e(x^2) + xP_o(x^2)\).
  • \(P_e(x^2), P_o(x^2)\) have degree 2.
  \[\begin{aligned} P(x_i) &= P_e(x_i^2) + x_iP_o(x_i^2)\\ P(-x_i) &= P_e(x_i^2) - x_iP_o(x_i^2) \end{aligned} \]

Generalization the observation to a polynomial with degree n-1

• We want evaluate at \(n\) points.
• We can split the polynomial into even and odd terms with smaller polynomials \(P_e(x^2), P_o(x^2)\) with degree \(\frac{n}{2}-1\).
• So how do we evaluate these polynomials with half the degree of our original polynomial?
  • This is just another evaluation problem. But this time we need evaluate the polynomials at each of our original inputs squared.
  • Evaluate \(P_e(x^2), P_o(x^2)\) each at \(x_1^2, x_2^2,\dots, x_{\frac{n}{2}}^2\). (\(\frac{n}{2}\) points).
  • Same process on simpler problem.
  • The start of recursive algorithm

Bigger picture

• We want to evaluate a polynomial \(P(x)\) at \(n\) points with positive and negative paired.
• \(P(x): [p_0, p_1,\dots,p_{n-1}]\) and \([\pm x_1, \pm x_2,\dots, \pm x_{\frac{n}{2}}]\).
• We split the polynomial: \(P(x) = P_e(x^2) + xP_o(x^2)\).
• We now have two simpler polynomials of degree \(\frac{n}{2} -1\) and only need \(\frac{n}{2}\) points to evaluate.
  • \(P_e(x^2): [p_0, p_2, p_4,\dots,p_{n-2}]\) and \([x_1^2, x_2^2,\dots, x_{\frac{n}{2}}^2]\).
    • \([P_e(x_1^2), P_e(x_2^2), P_e(x_4^2), \dots, P_e(x_{\frac{n}{2}}^2)]\).
  • \(P_o(x^2): [p_1, p_3, p_5,\dots,p_{n-1}]\) and \([x_1^2, x_2^2,\dots, x_{\frac{n}{2}}^2]\).
    • \([P_o(x_1^2), P_o(x_2^2), P_o(x_4^2), \dots, P_o(x_{\frac{n}{2}}^2)]\).
• Once we recursively evaluate these smaller polynomials we can then go through every point in our original set of \(n\) points and calculate the respective values by utilizing the relationship between the positive and negative paired points.

• This gives us the value representation of our original polynomial \(P(x)\)

• So, we have \(O(n \log n)\) Recursive Algorithm. Since the two recursive sub problems have half the size of the original problem and take linear time to evaluate \(n\) points.
• This would be huge improvement from our earlier quadratic running time. But

One major problem:

• The problem occurs at the recursive steps.
• The entire scheme relies on the fact that the polynomial will have positive and negative paired points for evaluation.
• This works at the top level but next level we are evaluating \(\frac{n}{2}\) points where each point is squared value.
• These all end up being positive so the recursion breaks.

• The natural question is can we make these new set of points \([x_1^2, x_2^2,\dots, x_{\frac{n}{2}}^2]\), \(\pm\) paired?
• Ingenious Idea behind FFT: The only way this is possible is if we expand the domain of possible initial points include complex number.
• For special choice of complex numbers the recursive relation works perfectly where every subsequence set of points will contain \(\pm\) pairs.
• What possible set of initial \(n\) points has this property?

What possible set of initial n points has this property?

• This is a hard question and to answer it we’re going to do a little bit of reverse engineering with an example.
• Let \(P(x) = x^3 + x^2 - x - 1\).
• Which requires at least \(n = 4\) points for its value representation.
• These points need to \(\pm\) pairs. So we can write them as \(x_1, -x_1, x_2, -x_2\).
• We know that the recursive steps require that we evaluate the odd and even split of the polynomial at two points \(x_1^2, x_2^2\).
• Key constraint here is that for the recursion to work these two points also have to be \(\pm\) pairs.
• So we have an equivalence between \(x_2^2\) and \(-x_1^2\).
• At the bottom level of the recursion will have single point \(x_1^4\)
• \(x_1 = 1\) then \(-x_1 = -1\) implies \(x_1^2 = 1. Then \)x_2^2\(should be -1. Then we have to choose,\)x_2 = i, -x_2 = -i\(. then \)x_1^4 = 1$
• Alternative Perspective is Solution \(x^4 = 1\). Since the bottom layer of the recursion the value of any of our original points to the power 4 was 1.
• We know this equation has 4 solutions. All of which are encompassed by a special set of points called the 4th roots of unity.
• Generalization..

Another example

• Let \(P(x) = x^5 + 2x^4 - x^3 + x^2+ 1\).
• Need \(n \geq 6\) points. It is convenient choose power of 2. So, let \(n = 8\).
• The result \(x_i^8 = 1\)
• The points are \(8^{\text{th}}\) roots of unity.

Generalization of n’th roots of unity

• Let \(P(x) = p_0 + p_1x + p_2x^2 + \dots + p_dx^d\)
• Need \(n \geq d+1\) points, \(n = 2^k,\space k\in\Z\).
• The result \(x_i^n = 1\)
• The points are \(n^{\text{th}}\) roots of unity.

Visualize roots of unity

• \(n^{th}\) roots of unity
• \(n\) roots of unity
  • \(z^n = 1\).
  • Evaluate \(P(x)\) at \([1, \omega^1, \omega^2, \dots, \omega^{n-1}]\).
  • \((\omega^j, \omega^{j+\frac{n}{2}})\) are \(\pm\) paired. Because \(-\omega^j = \omega^{j+\frac{n}{2}}\).
• \(\frac{n}{2}\) roots of unity.
  • Then evaluate \(P_e(x^2), P_o(x^2)\) at \([1, \omega^2, \omega^4, \dots, \omega^{\frac{n}{2}-1}]\).

Code FFT

• Let \(P: [p_0,p_1,\dots, p_{n-1}]\) and \(n\) in power of 2.