6
$\begingroup$

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 distinct 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*}

Initially, $R(x) = N'(x)$. Furthermore, the dividend $R$ has degree $\le 2n-1$ while the divisor has degree $n$. Initially $n = k/2$, 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.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ If $x_i$ are the $k$-th power roots of unity, then $N(x)=x^k-1$ and $N'(x)=kx^{k-1}$ can be trivially evaluated at any point. $\endgroup$
    – Max Alekseyev
    Commented Apr 18, 2018 at 4:04
  • 1
    $\begingroup$ Thank you! I messed up but updated the post: The $x_i$'s can be an $\ell$th root of unity for some $\ell > k$ but they won't always be the $i$th $\ell$th root of unity. In other words, it's possible to have $x_1 = \omega^2, x_2 = \omega^5, x_3 = \omega^7, \dots$. $\endgroup$
    – Alin Tomescu
    Commented Apr 18, 2018 at 18:40
  • $\begingroup$ If $g(x)=\prod (x-x_i)$ with $x_i$ all distinct, and $f$ is any polynomial, then the remainder of $f$ upon division by $g$ is (by Lagrange Interpolation) $$ \sum f(x_i) \frac{(\partial _i g)(x_i)}{g'(x_i)}.$$ I don't know if that is convenient to you. $\endgroup$
    – Venkataramana
    Commented Apr 24, 2018 at 1:47
  • 1
    $\begingroup$ In the first formula above I should have written $(\partial _i g)(x)$ and not $(\partial _i g)(x_i)$ $\endgroup$
    – Venkataramana
    Commented Apr 24, 2018 at 2:06
  • 1
    $\begingroup$ Oh, I see. It's basically the Lagrange formula applied to $f(x) \bmod \prod (x-x_i)$. Never saw it stated in this way before. Thank you! Unfortunately, not sure how I can make use of it. The reason I'm asking about computing remainders fast is precisely because I want to speed up Lagrange interpolation itself. Computing your formula naively would take $O(n^2)$ time when $\deg{g} = n$. Computing it asymptotically faster reduces to computing remainders fast! $\endgroup$
    – Alin Tomescu
    Commented Apr 24, 2018 at 2:19

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .