Polynomial Multiplication (Vector Convolution) and FFT

对一个次数界为 \(n\) 的多项式 \(A(x)=\sum_{j=0}^{n-1}a_j x^j\) 而言，其系数表达是一个由系数组成的向量 \(a=(a_0, a_1, \cdots, a_{n-1})\) 。

采用系数表达对于多项式的某些运算是很方便的。例如，对多项式 \(A(x)\) 在给定点 \(x_0\) 的求值运算就是计算 \(A(x_0)\) 的值。使用霍纳法则，我们可以在 \(\Theta(n)\) 时间复杂度内完成求值运算： \[A(x_0) = a_0 + x_0(a_1 + x_0(a_2 + \cdots + x_0(a_{n-2} + x_0(a_{n-1})) \cdots ))\]

类似地，对两个分别用系数向量 \(a = (a_0, a_1, \cdots, a_{n-1})\) 和 \(b=(b_0, b_1, \cdots, b_{n-1})\) 表示的多项式进行相加时，设结果多项式的系数向量为 \(c=(c_0, c_1, \cdots, c_{n-1})\) ，则 \(c_j = a_j + b_j\) ，显然所需的时间是 \(\Theta(n)\) 。

现在来考虑两个用系数形式表示的、次数界为 \(n\) 的多项式 \(A(x)\) 和 \(B(x)\) 的乘法运算。如果直接使用定义多项式乘法时的公式，那么完成多项式乘法所需时间就是 \(\Theta(n^2)\) ，因为向量 \(a\) 中的每个系数必须与向量 \(b\) 中的每个系数相乘。本文的主要目标就是 讨论如何降低多项式乘法的时间复杂度。

一个次数界为 \(n\) 的多项式 \(A(x)\) 的点值表达就是一个由 \(n\) 个点值对所组成的集合 \[\{(x_0, y_0), (x_1, y_1), \cdots, (x_{n-1}, y_{n-1})\}\] 其中 \(y_k=A(x_k)\) ，且对 \(k=0,1,\cdots, n-1\) ，所有 \(x_k\) 各不相同。

一个多项式可以有很多不同的点值表达，因为可以采用 \(n\) 个不同的点 \(x_0, x_1, \cdots, x_{n-1}\) 构成的集合作为这种表示方法的基。

对一个用系数形式表达的多项式来说，在原则上计算其点值表达是简单易行的，因为我们所要做的就是选取 \(n\) 个不同 \(x_0, x_1, \cdots, x_{n-1}\) ，然后对 \(k=0,1, \cdots, n-1\) 求出 \(A(x_k)\) 。根据霍纳法则，求一个点值所需时间复杂度为 \(\Theta(n)\) ，求这 \(n\) 个点值所需时间复杂度为 \(\Theta(n^2)\) 。在稍后可以看到， 如果我们巧妙地选取点 \(x\) ，就可以加速这一计算过程，使其运行时间变为 \(\Theta(n \lg n)\) 。

从一个多项式的“点值表达”确定其“系数表达”形式称为“插值”。下面定理说明， 当插值多项式的“次数界”等于已知的点值对的数目时，插值是明确的。

定理（插值多项式的唯一性）：对于任意 \(n\) 个点值对组成的集合 \(\{(x_0, y_0), (x_1, y_1), \cdots, (x_{n-1}, y_{n-1})\}\) ，其中所有的 \(x_k\) 都不同；那么存在唯一的次数界为 \(n\) 的多项式 \(A(x)\) ，满足 \(y_k=A(x_k), k=0,1, \cdots, n-1\) 。

这个定理表明，给定任意两个不同点，就可以唯一地确定一条直线（即一次多项式）；给定任意三个不同点，就可以唯一地确定一条抛物线（即二次多项式）。需要注意，上面定理表述中使用的是“次数界”，而不是“次数”，这两者的关系参见节 1 。

拉格朗日公式： \[A(x) = \sum_{k=0}^{n-1} y_k \frac{\prod_{j \neq k} (x - x_j)}{\prod_{j \neq k}(x_k - x_j)}\] 可以完成这个插值操作，不过拉格朗日公式的时间复杂度为 \(\Theta(n^2)\) ，我们在本文中并不会采用它。

因此， \(n\) 个点的求值运算与插值运算是定义完备的互逆运算，它们将多项式的系数表达与点值表达进行相互转化。

对许多多项式相关的操作，点值表达是很便利的。对于加法，如果 \(C (x) = A (x) + B(x)\) ，则对任意点 \(x_k\) ，满足 \(C(x_k) = A(x_k) +B(x_k)\) 。更准确地说，如果已知 A 的点值表达 \[\{(x_0, y_0), (x_1, y_1), \cdots, (x_{n-1}, y_{n-1})\}\] 和 B 的点值表达 \[\{(x_0, y_0'), (x_1, y_1'), \cdots, (x_{n-1}, y_{n-1}')\}\] （注意，A 和 B 在相同的 \(n\) 个位置求值），则 C 的点值表达是 \[\{(x_0, y_0+y_0'), (x_1, y_1+y_1'), \cdots, (x_{n-1}, y_{n-1} + y_{n-1}')\}\]

因此，对两个点值形式表示的次数界为 \(n\) 的多项式相加，所需时间复杂度为 \(\Theta(n)\) 。

类似地，对于多项式乘法，点值表达也是方便的。如果 \(C(x) = A(x)B(x)\) ，则对于任意点 \(x_k\) ， \(C(x_k) = A(x_k)B(x_k)\) ，并且对 A 的点值表达和 B 的点值表达进行“逐点相乘”，就可得到 C 的点值表达。不过，我们也必须面对这样一个问题，即 \(degree(C) = degree (A) + degree (B)\) ，参见节 1.2 。这意味着对于次数界为 \(n\) 的多项式 \(A(x)\) 和 \(B(x)\) ，如果我们分别取 \(n\) 个点值对，则它们逐点相乘后得到的 \(C\) 并不是确定的（因为 \(C\) 的次数会变大，但逐点相乘后点值对的数目不变，由上一节的知识可知这无法通过插值唯一地确定 \(C\) ）。为了解决这个问题，对于次数界为 \(n\) 的多项式 \(A(x)\) 和 \(B(x)\) ，我们取 \(n\) 个点值对不够，要“扩展”为取 \(2n\) 个点值对参与计算。

给定 \(A\) 的扩展点值表达： \[\{(x_0, y_0), (x_1, y_1), \cdots, (x_{2n-1}, y_{2n-1})\}\] 和 \(B\) 的对应扩展点值表达： \[\{(x_0, y_0'), (x_1, y_1'), \cdots, (x_{2n-1}, y_{2n-1}')\}\] 则多项式 \(A\) 和 \(B\) 的乘积 \(C\) 的点值表达为： \[\{(x_0, y_0y_0'), (x_1, y_1y_1'), \cdots, (x_{2n-1}, y_{2n-1} y_{2n-1}')\}\]

给定两个点值扩展形式的输入多项式，我们可以看到使其相乘而得到点值形式的结果需要 \(\Theta(n)\) 时间，比采用系数形式表达的多项式相乘所需时间少得多。