A simple way to understand the transposed algo of multi-eval
A simple way to understand the transposed algorithm of multi-point evaluation of polynomials in Tellegen’s Principle into Practice.
I learned this from Bernstein's paper Scaled Remainder Trees. If there are any mistakes, please tell me, thanks! (Sorry for my poor English)
Let $$$\mathbb{R}((x))$$$ denote the ring of formal Laurent series, $$$\mathbb{R}\lbrack x\rbrack$$$ denote the ring of polynomial. $$$f(x)\bmod 1:=f_{-1}x^{-1}+f_{-2}x^{-2}+\cdots$$$.
Bernstein showed that division in $$$\mathbb{R}\lbrack x\rbrack$$$ is division in $$$\mathbb{R}((x^{-1}))$$$. Here is a concrete example. Let $$$A(x):=1+x+4x^2+5x^3+x^4+4x^5\in\mathbb{R}\lbrack x\rbrack$$$ and $$$B(x):=1+9x+8x^2+x^3\in\mathbb{R}\lbrack x\rbrack$$$, we want to compute $$$Q(x),R(x)\in\mathbb{R}\lbrack x\rbrack$$$ such that $$$A(x)=B(x)Q(x)+R(x)$$$ and $$$\deg R(x)\lt \deg B(x)$$$ (with $$$\deg 0=-\infty$$$). Let's do this in $$$\mathbb{R}((x^{-1}))$$$. First, we should find the multiplicative inverse of $$$B(x)$$$ which is
and compute
We could find that $$$Q(x)$$$ is exactly $$$A(x)B^{-1}(x)-(A(x)B^{-1}(x)\bmod 1)$$$, and the leading coefficient of $$$R(x)$$$ equals $$$[x^{-1}]A(x)B^{-1}(x)$$$. That's not a coincidence. Consider the simplest case
So we have $$$f(v)=[x^{-1}]f/(x-v)$$$ cause
The problem of multi-point evaluation is as follows: Given polynomial $$$f(x)=\sum_{i=0}^nf_ix^i$$$ and $$$v_0,v_1,\dots ,v_n$$$, print $$$f(v_0),f(v_1),\dots ,f(v_n)$$$.
The traditional algorithm for multi-point evaluation is that we make an almost balanced binary (sub)product tree with leaves are polynomials $$$p_i(x)=x-v_i$$$ and non-leaf nodes are the product of its children. Then we compute $$$f\bmod (p_1\cdots p_n)$$$ and then compute $$$f\bmod (p_1\cdots p_{n/2})$$$ and $$$f\bmod (p_{n/2+1}\cdots p_n)$$$ cause $$$(f\bmod (p_1\cdots p_n))\bmod (p_1\cdots p_{n/2})=f\bmod (p_1\cdots p_{n/2})$$$ (suppose $$$n$$$ is even) and then ... The transposed algorithm is that we compute $$$f/(p_1\cdots p_n)$$$ and $$$f/(p_1\cdots p_n)\cdot (p_{n/2+1}\cdots p_{n})=f/(p_1\cdots p_{n/2})$$$, finally we will have $$$f/p_i$$$ at the leaf of the tree, the coefficient of $$$x^{-1}$$$ is exactly what we want. The only remaining problem is how many terms should we track when doing the computation. It's clear that we don't care about the coefficients of $$$x^0,x^1,\dots$$$ in $$$f/(p_1\cdots p_n)$$$ cause they do nothing with the coefficient of $$$x^{-1},x^{-2},\dots$$$ when $$$f/(p_1\cdots p_n)$$$ was multiplied by a polynomial like $$$g_0+g_1x+g_2x^2+\cdots$$$. Another observation is that for $$$f/P\bmod 1=a_{-1}x^{-1}+a_{-2}x^{-2}+\cdots +a_{-\deg P}x^{\deg P}+\cdots$$$, only $$$a_{-1},\dots ,a_{-\deg P}$$$ are enough. Consider a very simple case that we have $$$f/(p_1p_2)\bmod 1=c_{-1}x^{-1}+c_{-2}x^{-2}+c_{-3}x^{-3}+\cdots$$$ and want to compute $$$f/p_1\bmod 1$$$ via multiplying $$$f/(p_1p_2)\bmod 1$$$ by $$$p_2$$$, the coefficients of $$$x^{-3},x^{-4},\dots$$$ have no effect on the coefficient of $$$x^{-1}$$$ (it's more complicated for the integer case). So we could almost halve the size of problem after one multiplication.
About how to compute $$$(p_1\cdots p_n)^{-1}$$$ in $$$\mathbb{R}((x^{-1}))$$$, we could simply use the method that we compute the multiplicative inverse of formal power series $$$x^{\deg(p_1\cdots p_n)}p_1(x^{-1})\cdots p_n(x^{-1})$$$ in $$$\mathbb{R}\lbrack \lbrack x\rbrack \rbrack$$$.
