Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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)$.

share|improve this answer
    
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). –  Emil Jeřábek May 9 '11 at 17:47
    
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. –  Klim Efremenko May 9 '11 at 20:03
    
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. –  Emil Jeřábek May 10 '11 at 10:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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