FFT

多项式的多点求值与快速插值

Posted by miskcoo on May 25, 2015

多项式的多点求值(multi-point evaluation)是给出一个多项式 $A(x)$,和 $n$ 个点 $x_0, x_1, \cdots, x_{n-1}$,要求求出 $A(x_0), A(x_1), \cdots, A(x_{n-1})$

相反的,多项式的插值(interpolation)是给出 $n+1$ 个点 $(x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n)$,求出一个 $n$ 次多项式,使得这些点都在这个多项式上

这两个问题实际上是在多项式的点值表示(point-value representation)和系数表示(coefficient representation)之间转换的方法,在快速傅里叶变换中由于带入值的特殊性质,可以在 $\mathcal O(n\log n)$ 的之间内将两种东西互相转换,但是,如果是任意给定点要求求值或者插值,就没有比较好的性质可以利用,但是仍然有比较快速的方法来计算它们

多项式的多点求值

给出一个多项式 $A(x)$,和 $n$ 个点 $x_0, x_1, \cdots, x_{n-1}$,如果要求 $A(x)$ 在各个点处的值直接处理肯定是比较慢的,而且似乎也没有什么优化的空间,现在试试看能不能像在进行快速傅里叶变换的时候一样,用分治来把问题规模减少

有两种方法,一是先把系数分成两半,另一种是先把要求的值分成两半,但是最后要求的是两个都要分成两半才可以把问题的规模减半。我们把要求的值分成两半

\[\begin{eqnarray*} X^{[0]} &=& \{x_0, x_1, \cdots, x_{\lfloor \frac{n}{2} \rfloor}\} \\ X^{[1]} &=& \{x_{\lfloor \frac{n}{2} \rfloor+1},x_{\lfloor \frac{n}{2} \rfloor+2}, \cdots, x_{n-1}\} \end{eqnarray*}\]

现在考虑的是如何才可以把系数减半,我们来想想倒过来的过程,现在已经求出了这 $\lfloor \frac{n}{2} \rfloor$ 个值,如果插值回来的话,得到的多项式的次数是 $\lfloor \frac{n}{2} \rfloor$,我们记用 $X^{[0]}, X^{[1]}$ 插值得到的多项式为 $A^{[0]}(x), A^{[1]}(x)$,这样的话如果可以求出它们,就可以把整个问题的规模减半了

考虑这两个多项式

\[\begin{eqnarray*} P^{[0]}(x) &=& \prod_{i=0}^{\lfloor \frac{n}{2} \rfloor} (x-x_i) \\ P^{[1]}(x) &=& \prod_{i=\lfloor \frac{n}{2} \rfloor+1}^{n-1} (x-x_i) \end{eqnarray*}\]

这两个多项式分别在 $x \in X^{[0]}$ 和 $x \in x^{[1]}$ 的时候为 $0$,而且次数都是我们要求的 $\lfloor \frac{n}{2} \rfloor$,现在可以把 $A(x)$ 表示成这样

\[A(x) = D(x)P^{[0]}(x) + A^{[0]}(x)\]

这样得到的 $A^{[0]}(x)$ 满足在 $x \in x^{[0]}$ 的时候 $D(x)P^{[0]}(x)$ 是 $0$,这样的话 $A(x) = A^{[0]}(x)$,因此就表示出了 $A^{[0]}(x)$

再看这个式子,相当于是多项式的求模(不会看我这篇文章),也就是

\[A^{[0]}(x) \equiv A(x) \pmod {P^{[0]}(x)}\]

对于 $X^{[1]}$ 的部分,处理方法也是一样的

最后多项式求模的时间复杂度是 $\mathcal O(n \log n)$,那么多项式多点求值的时间复杂度就是

\(T(n) = 2T(\frac{n}{2}) + \mathcal O(n \log n) = O(n \log^2 n)\)

多项式的快速插值

好,现在来看多项式的插值,给出了 $n + 1$ 个点的集合

\[X = \{(x_i, y_i) : 0 \leq i \leq n\}\]

现在要求一个 $n$ 次多项式 $A(x)$ 满足 $\forall (x, y) \in X, A(x) = y$

如果直接用 Lagrange 插值公式来进行插值,那么时间复杂度是 $\mathcal O(n^2)$ 的,现在再来考虑分治方法,我们把要插值的点分成两半

\[\begin{eqnarray*} X^{[0]} &=& \{(x_i, y_i) : 0 \leq i \leq \lfloor \frac{n}{2} \rfloor \} \\ X^{[1]} &=& \{(x_i, y_i) : \lfloor \frac{n}{2} \rfloor < i \leq n\} \end{eqnarray*}\]

现在假设已经求出了 $X^{[0]}$ 的插值多项式 $A^{[0]}(x)$,考虑如何修改它使得它变成 $A(x)$,假设

\[P(x) = \prod_{i=0}^{\lfloor \frac{n}{2} \rfloor} (x-x_i)\]

那么构造 $A(x)$,使其满足

\[A(x) = A^{[1]}(x)P(x) + A^{[0]}(x)\]

其中 $A^{[1]}(x)$ 是一个未知的多项式,由于 $\forall (x, y) \in X^{[0]}, P(x) = 0, A^{[0]}(x) = y$,这样的话就满足 $X^{[0]}$ 的点都在 $A(x)$ 上,问题就变成要将 $X^{[1]}$ 内的点插值,使得

\[\forall (x_i, y_i) \in X^{[1]}, y_i = A^{[1]}(x_i)P(x_i) + A^{[0]}(x_i)\]

化简之后得到

\[A^{[1]}(x_i) = \frac{A^{[0]}(x_i)-y_i}{P(x_i)}\]

这样就得到了新的待插值点,利用同样的方法求出插值出 $A^{[1]}$ 然后合并就可以了

由于每一次都要多点求值求出 $X^{[1]}$ 内 $P(x)$ 和 $A^{[0]}(x)$ 的值,最终复杂度是

\[T(n) = 2T(\frac{n}{2}) + \mathcal O(n \log^2 n) = \mathcal O(n \log^3 n)\]

代码?我还没写出来有空再贴

Update 2019.7.25: 这个坑终于有人填了,代码可以看这里