<p>Symbolic multiplication of degree $&lt;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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-11-26T07:24:58.050Z
2015-11-26T07:24:58.050Z
Thomas Steinke
<p>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 <code>n-1</code> degree vectors <code>a</code> and <code>b</code> as polynomials <code>A(x)</code> and <code>B(x)</code> and use that to compute the convolution <code>c</code> of the two vectors <code>a</code> and <code>b</code>.</p>

<p>However I am unable to understand the reason behind the next set of statements which goes this way - ... Now, rather than multiplying <code>A</code> and <code>B</code> symbolically, we can treat them as functions of the variable <code>x</code> and multiply them as follows.
First we choose 2 * n values <code>x_1</code>, <code>x_2</code>, . . . , <code>x_2n</code> and evaluate <code>A(x_j)</code> and <code>B(x_j)</code> for each of <code>j</code> = 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 <code>A</code> and <code>B</code></p>

<ds.algorithms>
Choosing 2*n values while evaluating Fast Fourier Transform
rgk
# Choosing 2*n values while evaluating Fast Fourier Transform

(Asked by: username_0 on 2015-11-26)

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`

**Tags:** ds.algorithms


---

## 1 answers

### Answer by username_1 on 2015-11-26. Score: 3 | Accepted answer

Symbolic multiplication of degree $

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.


---

