4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.