0
$\begingroup$

I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the multiplication of 2 polynomials using their value representation works.

The screenshot below is from a Reducible video (at time 6:39) that explains the Fast Fourier transform. I see that we need 5 points to get $C(x)$, which is of degree $4$, but I don't see how multiplying say the first point of $A(x)$ and $B(x)$, that is, $(-2,1) \times (-2,9)$ gives $(-2,9)$

There's a similar answer here but the steps aren't provided just the final answer, which still baffles me.

Reducible screenshot

$\endgroup$

1 Answer 1

3
$\begingroup$

If $P, Q, R \in \mathbb{R}[X], R = PQ$, then for any $x \in \mathbb{R}$, $R(x) = P(x)\times Q(x)$.

It means that if the value representation of $P$ is $[(x_1, P(x_1)); (x_2, P(x_2)); …, (x_n, P(x_n))]$ and the value representation of $Q$ is $[(x_1, Q(x_1)); (x_2, Q(x_2)); …, (x_n, Q(x_n))]$, then the value representation of $R$ is $[(x_1, P(x_1)Q(x_1)); (x_2, P(x_2)Q(x_2)); …, (x_n, P(x_n)Q(x_n))]$.

In your example, $(-2, 1)$ represents a couple $(x_i, P(x_i))$ and $(-2, 9)$ is $(x_i, Q(x_i))$, so it's normal that $(x_i, R(x_i))$ is $(-2, 1\times 9) = (-2, 9)$.

$\endgroup$
1
  • $\begingroup$ Thank you. I didn't realize that I needed to just multiply the $y$ values, what is $R(x)$ in your example, and that the $x$ remains the same. $\endgroup$ Commented Apr 11, 2021 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.