转置原理与多点求值

转置原理

转置原理，或称特勒根原理（Tellegen’s Principle），指的是对于矩阵$\textbf{M}$和向量$\textbf{v}$，为优化计算$\textbf{Mv}$，我们可以考察$\textbf{M}^T\textbf{v}$的计算方法。原因是设有分解$\textbf{M}=\textbf{E}_1\cdots\textbf{E}_k$，那么$\textbf{M}^T=\textbf{E}_k^T\cdots\textbf{E}_1^T$。

也就是说，如果$\textbf{M}^T\textbf{v}$有快速的计算方法，那么$\textbf{M}\textbf{v}$在原理上也一定拥有相同复杂度的算法。

多项式多点求值

多点求值（multi point evaluation），指的是给出多项式$F(x)=\sum_{i=0}^{n-1}f_ix^i$以及$n$个横坐标$a_0,a_1,\cdots,a_{n-1}$，快速求出$F(a_0),F(a_1),\cdots,F(a_{n-1})$。目前已有的算法是通过多项式取模来实现。

注意到，多点求值本质上是对向量$\textbf{v}=[f_0,\cdots,f_{n-1}]^T$做一个线性变换：

$$\begin{bmatrix} 1 & a_0 & a_0^2 & \cdots & a_0^{n-1}\\ 1 & a_1 & a_1^2 & \cdots & a_1^{n-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & a_{n-1} & a_{n-1}^2 & \cdots & a_{n-1}^{n-1}\\ \end{bmatrix} \begin{bmatrix} f_0 \\ f_1 \\ \vdots \\ f_{n-1} \end{bmatrix}= \begin{bmatrix} F(a_0) \\ F(a_1) \\ \vdots \\ F(a_{n-1}) \end{bmatrix}$$

这个矩阵是一个范德蒙德矩阵，记作$\textbf{V}$。我们把矩阵转置一下得到

$$\textbf{V}^T\textbf{v}=\begin{bmatrix} 1 & 1 & 1 & \cdots & 1\\ a_0 & a_1 & a_2 & \cdots & a_{n-1}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_0^{n-1} & a_1^{n-1} & a_2^{n-1} & \cdots & a_{n-1}^{n-1}\\ \end{bmatrix} \begin{bmatrix} f_0 \\ f_1 \\ \vdots \\ f_{n-1} \end{bmatrix}$$

观察发现，转置后的变换，向量的第$j$项求的是$\sum_{i=0}^{n-1}f_ia_i^j$。写出它的生成函数，因此我们求的是

$$\sum_{j\ge 0}x^j\sum_{i=0}^{n-1}f_ia_i^j=\sum_{i=0}^{n-1}\frac{f_i}{1-a_ix}$$

这个多项式的前$n$项的系数（对$x^n$取模）。这个东西可以分治多项式乘法计算。

那么我们把这个矩阵转置回去，就可以得到多点求值的算法。也就是说本质上我们可以把所有初等变换写下来，然后转置一下并反转这个操作序列，然后再照着做一遍，就得到了相同复杂度的多点求值做法。但是这个过于憨批，想必没人会去实现它。为此我们需要分析计算$\textbf{V}^T\textbf{v}$的过程中变换的转置变换是什么。

初等变换

本质上我们进行的变换有如下两种：

• 把变量$x$乘一个常数$c$，记作$x\gets xc$。
• 把变量$x$乘$c$加到变量$y$上，记作$y\gets y+xc$。

注意，变量的交换可以使用上面两个操作完成。

它们的转置操作分别是

• 把变量$x$乘一个常数$c$，记作$x\gets xc$（不变）。
• 把变量$y$乘$c$加到变量$x$上，记作$x\gets x+yc$。

这个大家可以写出初等变换矩阵，然后转置一下，自行验证。

多项式乘法

多项式乘法的变换过程是，给出多项式$F(x)=f_0+\cdots+f_{n-1}x^{n-1}$和$G(x)=g_0+\cdots+g_{m-1}x^{m-1}$，那么对于$H(x)=F(x)G(x)$，有$h_{i+j}\gets h_{i+j}+f_ig_j$，其中$0\le i<n,0\le j<m$。

我们设$g$是一个常数多项式，而$f$是输入。那么这个变换的转置就是：$h_i\gets h_i+f_{i+j}g_j$，其中$0\le i+j<n,0\le j<m$。容易发现，这样求出的$h$有$n$项。我们记这个变换是$h=f\otimes g$。

这个可以倒过来 NTT 计算。

转置后的算法

接下来我们具体考虑求$\sum_{i=0}^{n-1}\frac{f_i}{1-a_ix}$的算法。

设$g(x)=\prod_{i=0}^{n-1}(1-a_ix)$，那么我们可以先求出$\sum_{i=0}^{n-1}\frac{f_ig(x)}{1-a_ix}$，然后再乘上$g^{-1}$即可。

求$T(x)=\sum_{i=0}^{n-1}\frac{f_ig(x)}{1-a_ix}$的过程可以分治计算：

• 如果$n=1$，那么直接返回$f_i$。

• 否则，设$m=\lfloor \frac{n}{2} \rfloor$。

  • 令$T_L=\sum_{i=0}^{m-1}\frac{f_ig(x)}{1-a_ix}$，$T_R=\sum_{i=m}^{n-1}\frac{f_ig(x)}{1-a_ix}$。
  • 令$g_L=\prod_{i=0}^{m-1}(1-a_ix)$，$g_R=\prod_{i=m}^{n-1}(1-a_ix)$。
  • 那么有$T=T_Lg_R+T_Rg_L$，$g=g_Lg_R$。因此两边分别递归求$(T,g)$即可。

最后对于求出的$T$，乘上$g^{-1}$并对$x^n$取模。

由于多项式乘法的复杂度是$O(n\log_2n)$的，因此该算法的总复杂度为$O(n\log_2^2n)$。

还原转置

那么我们考虑多点求值的算法。

首先，我们操作是倒过来并且经过转置的。

其次，$g(x)$在算法过程中是常量（只和$a_i$有关，和$f_i$无关）。

把$f_i$当作输入，也就是说$T(x)=\sum_{i=0}^{n-1}f_ix^i$。

首先让$T=T\otimes g^{-1}$。注意，对$g$求逆的过程是对常量求逆的过程，因此不需要转置，直接多项式求逆。

然后我们把上述分治算法倒过来并转置：

• 如果$n=1$，则$T$是一个常数，直接返回$T$即可（存储到数组上）。
• 否则，设$m=\lfloor\frac{n}{2}\rfloor$。
  • 原本是$T=T_Lg_R+T_Rg_L$，转置后就变成了：$T_L=T\otimes g_R$，$T_R=T\otimes g_L$。
  • 并且$T_L$只需要保留前$m$项，$T_R$只需要保留前$n-m$项。
  • $g=g_Lg_R$是不变的，因为是常量。实际上这个应该是预处理的。

算法在叶子处的值就是对应的点值。

该算法的时间复杂度仍是$O(n\log_2^2n)$，但不用每次都多项式求逆，常数大大减小。

参考文献

QY 为什么可以 5e5 多点求值 (详细揭秘) - rqy

题解 P5050 【模板】多项式多点求值 - EI