-3
$\begingroup$

I am going through the Fast Fourier Transform technique mentioned in the Algorithm Design Book by John Kleinberg and Eva Tardos. I have understood why we need to interpret two n-1 degree vectors a and b as polynomials A(x) and B(x) and use that to compute the convolution c of the two vectors a and b.

However I am unable to understand the reason behind the next set of statements which goes this way - ... Now, rather than multiplying A and B symbolically, we can treat them as functions of the variable x and multiply them as follows. First we choose 2 * n values x_1, x_2, . . . , x_2n and evaluate A(x_j) and B(x_j) for each of j = 1, 2, . . . , 2 * n. Can someone explain why this step has been chosen? Specifically, the number 2 * n and what is preventing us from doing a symbolic multiplication of A and B

$\endgroup$

1 Answer 1

3
$\begingroup$

Symbolic multiplication of degree $<n$ polynomials $A(x)$ and $B(x)$ would take $O(n^2)$ time. That may be fine, but they are giving an algorithm that takes $O(n \log n)$ time, which is better.

Instead of symbolic multiplication, they are suggesting that you evaluate the polynomials at $2n$ points, multiply those values pointwise, and then interpolate the product polynomial (i.e. compute the coefficients of $A(x)B(x)$ from the values). The reason you need $2n$ points is that $A(x)B(x)$ could have degree $2n-2$ and you need more points than the degree to interpolate.

$\endgroup$

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