Hello, multivariate multiplication.

· · 个人记录

我们的目的是解决高维多项式乘法时的维度爆炸问题。也就是根据传统方法，我们在计算多项式乘法 f(x_1,\dots,x_k)\cdot g(x_1,\dots,x_k)\bmod (x_1^{n_1},\dots,x_k^{n_k}) 时，设 N = \prod_i n_i，若要先计算整个值域，则值域是 \Omega(N2^k) 量级的，更无论适合 DFT 的值域了。这里，我们提出一种方法计算 \Theta(kN\log N) 的多项式乘法方法。

接下来，我们将给出一个颇具构造性的算法，首先我们将一个下标 (i_1,\dots,i_k) 转化为一个「(n_1,\dots,n_k) 进制数」，即 i = i_1 + i_2\cdot n_1 + \cdots + i_k \cdot n_1\cdots n_{k-1}。这个转化有一个至关重要的好处，那就是 (i_1,\dots,i_k) 下标的加法对应于 i 下标的加法。只不过现在我们需要去掉加法发生了进位部分的贡献。

一个直觉是，我们应当设置一个合适的占位多项式，也就是先考虑某个占位函数 \chi(i) 使得 i+j 不进位当且仅当 \chi(i+j)=\chi(i)+\chi(j)。那么我们进行一个 \sum_i f_i x^i t^{\chi(i)} 的二元多项式乘法，其乘法就可以使得我们提取出实际的结果了。

那么问题来了，什么样的 \chi(i) 是较为合适的呢？借由子集卷积，容易想到的一者是 \chi(i)=\sum_j i_j，但当 n_j 很大的时候，这会让 \chi(i) 的值域非常大。我们不妨转换思维，如果对于每一个 i，都保证 \{ \chi(i-j)+\chi(j) | 0\le j\le i \} 这个集合很小的话，我们就可以通过对某个阈值 D 进行取模 \bmod (t^D-1)，如果对每个 i，前面描述的集合中每个数 \bmod D 互不相同，那么我们所要求的信息就还是可以成功保留的。

而回顾衡量进位的单位，我们惊喜地发现 \chi(i) = \left\lfloor \frac{i}{n_1}\right\rfloor + \left\lfloor \frac{i}{n_1n_2}\right\rfloor + \dots + \left\lfloor \frac{i}{n_1\cdots n_{k-1}}\right\rfloor 是一个很好的占位函数。由于 \left\lfloor \frac{i}{x}\right\rfloor + \left\lfloor \frac{j}{x}\right\rfloor - \left\lfloor \frac{i+j}{x}\right\rfloor\in \{-1,0\}，自然有 \chi(i)+\chi(j)-\chi(i+j) \in [-k+1,0]。因此，我们只需计算 \sum_i f_i x^i t^{\chi(i)} 在 \bmod (t^k-1) 下的多项式乘法。因为 k\le \log_2 N，比较有效的实现是做 k 个长为 2N 的 DFT，然后在 t 维暴力进行卷积，复杂度有 \Theta(kN\log N) + \Theta(k^2N) = \Theta(kN\log N)。

对于牛顿迭代法，我们有一个非常简洁的实现方式。我们先通过特殊进制数的转化，套用在一元多项式上常见的牛顿迭代法，然后卷积全部替换成前述的 \Theta(kN\log N) 的高维卷积即可。复杂度即为 \Theta(kN\log N)。

其正确性亦不难解释，因为高维卷积已经被考虑为带有占位多项式的 \sum_i f_i x^i t^{\chi(i)} 卷积，对其进行任何运算，只会产生一些 j < \chi(i) 的 x^it^j 项，且这些项不会再对形如 x^it^{\chi(i)} 项有贡献。因此我们实际上就是牛顿迭代的时候只维护这个多项式的 \chi(i) 所构成的上轮廓。

另一点巧妙的地方在于，我们可以直接考虑一个特殊的微分算子 \mathfrak DF 是 \sum_i if_ix^i，不难检验它满足常见的导数性质（对多元幂级数 f,g 有 \mathfrak D(fg)=f\mathfrak D g+g\mathfrak Df，以及对幂级数 f 和多元幂级数 g 有 \mathfrak D(f\circ g)=(f'\circ g) \cdot \mathfrak Dg），因此求导也可以保持一元多项式上的写法。

由此，我们得到了一种通用性极强的多元幂级数计算方法。而代价仅仅是乘以一个维数 k。