# Fastest method for evaluating the limit of the sign of a polynomial

Consider a multivariate polynomial $f(x) = f(x_1, \ldots, x_n)$ with maximum degree $d$. Following the linear symbolic perturbation scheme described in Seidel 1998, I want to evaluate the limit

$$\lim_{\epsilon \to 0^+} \textrm{sign}~ f(x + \epsilon y)$$

for some $x,y \in \mathbb{R}^n$. This limit is given by the lowest degree nonzero coefficient of the polynomial

$$g(\epsilon) = f(x + \epsilon y)$$

If the polynomial is given as an add/multiply expression DAG of size $m$, we can evaluate $f_i(x+ty)$ for each node $f_i$ of the expression DAG, which takes at most $O(m(d+1)^2)$ using naive polynomial multiplication (and probably less in practice since most nodes will have lower degree).

Alternatively (as noted in the paper), we could evaluate $g(\epsilon)$ for $\epsilon = 0, \ldots, n-1$ and use polynomial interpolation to recover the coefficients. This takes time $O(m(d+1)+h(d))$ where $h(d)$ is the time required for polynomial interpolation.

Question: Is there a faster method? In particular, is $O(m(d+1))$ possible?

As I was writing the question, I realized that in fact both of the given schemes achieve $O(m(d+1))$. This is because we always have $m \ge d$. In the expression tree scheme, the cost of quadratic polynomial multiplication at higher nodes in the tree can be amortized to lower nodes. In the polynomial interpolation scheme, at worst $h(d) = O(d^2)$ by precomputing the necessary matrices, and $O(m(d+1)+d^2) = O(m(d+1))$ since $m \ge d$. The polynomial interpolation scheme is also nicely modular, since it works even if $f(x)$ is given as a black box.