计算科学 - 评估多项式符号极限的最快方法 - 吾爱随笔录

考虑一个多元多项式 $f(x) = f(x_1, \ldots, x_n)$ 最大程度 $d$ . 遵循Seidel 1998中描述的线性符号扰动方案，我想评估极限

lim_{ϵ \to 0^{+}} sign f (x + ϵ y)

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

对于一些 $x,y \in \mathbb{R}^n$ . 该限制由多项式的最低次非零系数给出

g (ϵ) = f (x + ϵ y)

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

如果多项式给出为大小的加/乘表达式 DAG $m$ ，我们可以评估 $f_i(x+ty)$ 对于每个节点 $f_i$ 表达式 DAG，最多取 $O(m(d+1)^2)$ 使用朴素多项式乘法（实际上可能更少，因为大多数节点的度数较低）。

或者（如论文中所述），我们可以评估 $g(\epsilon)$ 为了 $\epsilon = 0, \ldots, n-1$ 并使用多项式插值来恢复系数。这需要时间 $O(m(d+1)+h(d))$ 在哪里 $h(d)$ 是多项式插值所需的时间。

问题：有更快的方法吗？特别是 $O(m(d+1))$ 可能的？