1
$\begingroup$

Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha) $ in $O(n)$ operations in $R$ for some $k >0$ . But could we compute $ f( X + \alpha ) $, or more generally compute $ f( \alpha X + \beta)$ in $O(n)$ or $O(n * ( \mathrm{log} \; n)^k )$ operations in $R$. Since the result is a polynomial in $X$ of degree at most $n$, I would guess there is a such way. But from the naive way, I can't just figure out a $O(n^2)$ algorithm to do this as follows: If $f(X) = \sum_{i=1}^n a_i X^i$, then one compute $g \leftarrow a_0, h \leftarrow \alpha X + \beta, g \leftarrow g+ a_{i+1} * h, h \leftarrow h* (\alpha X + \beta) $ for $0 \leq i \leq n-1$. In the $i$-th step, $g$ is a polynomial of degree $i$ and $h$ is a polynomial of degree $i+1$, so we need $O(i)$ operations in $R$ to compute $ g+ a_{i+1} * h$ and $h* (\alpha X + \beta) $, so the total operations needed is $O(n^2)$.

Is there any way to do so in $O(n)$ or $O(n * ( \mathrm{log} \; n)^k )$ operations in $R$? I don't really need to know how the algorithm works, I just need an explicit reference which says this is possible.

$\endgroup$

1 Answer 1

4
$\begingroup$

The answer is yes. You can do it using Fast Fourier Transform(FFT) to make FFT you need $n \log^k n$ operations. You not really need to know what FFT do. You need only to know that you can evaluate polynomial at some $n$ points using one FFT and you can calculate the polynomial from its values at $n$ points in one FFT.

The following algorithm should work: Using FFT evaluate $F(aX+b)$ at n points it is the same as to calculate F(X) at $n$ points. Next again using FFT you can calculate $F(aX+b)$.

$\endgroup$
3
  • $\begingroup$ You might need to work in an extension of $R$ to make the FFT work (you need a primitive $n$th root of unity or so). $\endgroup$ May 9, 2011 at 17:47
  • $\begingroup$ Yes, you are right I am litle bit simplifing the situation. I saw the paper which do it for arbitary algebra, but I can not remember where I saw it. $\endgroup$ May 9, 2011 at 20:03
  • $\begingroup$ Cantor and Kaltofen dx.doi.org/10.1007/BF01178683 do polynomial multiplication over any algebra. Presumably the same form of FFT could be used here. $\endgroup$ May 10, 2011 at 10:54

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.