Computation for composition of polynomials - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T19:47:02Z http://mathoverflow.net/feeds/question/64391 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64391/computation-for-composition-of-polynomials Computation for composition of polynomials unknown (google) 2011-05-09T13:49:48Z 2011-05-09T14:37:40Z <p>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)$.</p> <p>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.</p> http://mathoverflow.net/questions/64391/computation-for-composition-of-polynomials/64393#64393 Answer by Klim Efremenko for Computation for composition of polynomials Klim Efremenko 2011-05-09T14:00:40Z 2011-05-09T14:37:40Z <p>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. </p> <p>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)$. </p>