Note: Originally asked on Math StackExchange here, without an answer. Figured I should try here, since this is a more research-level question.

I am trying to implement a fast polynomial multipoint evaluation algorithm via FFT (e.g., the one described in Chapter 10.1 of "Modern Computer Algebra," 3rd edition). I should mention that the polyonomial being evaluated is the formal derivative $N'(x)$ of: $$N(x) = (x-x_1)(x-x_2)\cdots(x-x_k)$$

Specifically, we're evaluating $N'(x)$ at points $x_1, x_2, \dots, x_k$, where $k$ is a power of two.

I'm looking for any mathematical tricks that will lead to practical improvements in the multipoint evaluation algorithm. AFAICT, the main bottleneck will be computing remainders after division by $(x - x_i)\cdots(x-x_j)$.

As a refresher, at any "node" in the multipoint evaluation tree, we have a subset of points $x_i, \dots, x_j, x_{j+1}, \dots, x_\ell$, a previous remainder $R(\cdot)$, and we want to compute: \begin{align*} R(x) &\bmod (x - x_i)\cdots(x-x_j)\\ R(x) &\bmod (x - x_{j+1})\cdots(x-x_\ell) \end{align*} Furthermore, the dividend $R$ has degree $\le 2n-1$ while the divisor has degree $n$. Initially $n = k$, so it's a power of two, and then $n$ gets halved as we go down the multipoint evaluation tree.

I am aware there is a $O(n\log{n})$ algorithm based on FFT for computing remainders. For example, the "reversal-based" algorithm described in Chapter 9.1 of "Modern Computer Algebra," 3rd edition first computes the quotient by computing a modular inverse and then computes the remainder. (There is also a "reciprocal-based" algorithm described in Chapter 8.3 of "The Design and Analysis of Computer Algorithms," but I suspect this is slower.)

Is there any way to speed up this reversal-based division algorithm given our particular setting:

• We do not need the quotient, only the remainder.
• We only need to divide by $(x - x_i)\cdots(x-x_j)$, for some $i,j$ where $1 \le i,j \le k$.
• $x_i$ can be an $\ell$th root of unity ($\ell > k$) but not necessarily the $i$th one (or $i-c$th one)
• $k$ is a power of two or can be adjusted as needed
• We're doing a multipoint evaluation on $N'(x)$

The only mathematical trick I could find was in Todd Mateer's "Fast Fourier Transform Algorithms with Applications" PhD thesis (pdf), in Sec 7.5, pg 194.