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$。