7. 快速傅里叶变换¶
7.1. 快速傅里叶变换¶
在本模块中，我们继续讨论如何加速大多项式的乘法。 回忆一下，我们可以通过下面的过程得到两个多项式相乘的结果： 在足够多的点上对两者求值， 对求值结果逐对相乘，然后 用插值从所得的值构造出解多项式。 在多项式上的任意点这样做并不比 暴力乘法更快，因为对 \(n\) 个点的求值和插值 通常都需要 \(\Theta(n^2)\) 时间。 但在本模块中我们表明，我们能够找到一种利用 对称性来加速这一过程的方法。
在 0 处对任何多项式求值都很容易，因为只有常数项 非零。 在 1 或 -1 处求值相对容易，因为我们不需要真正 去乘 \(x\) 的值。 如果我们 同时 在 1 和 -1 处求值， 就能在两次求值之间共享大量工作。 再次考虑多项式 \(A = x^2 + 1\) 和 \(B = 2x^2 -x + 1\) 相乘。 因为最终结果是一个 4 次多项式， 我们需要五个点才能确定多项式 \(AB\)。 幸运的是，对于任意一对值 \(c\) 和 \(-c\)，我们都能加快处理。 这似乎表明了一些有希望的方法，可以加速多项式 求值的过程。 但是，用大致求一个点的相同时间求两个点， 只是把过程加速了一个常数因子。 有没有办法推广这些观察结果，进一步加速？ 而且，即使我们确实找到了快速求多个点的方法， 我们还需要对这些值插值，把 \(AB\) 的系数 找回来。
所以我们看到， 如果 能找到一个快速的方法 对 \(2n + 1\) 个点做求值／插值的话，我们在少于 \(\Theta(n^2)\) 次操作内就能让两个多项式相乘。 在进一步考虑这可能如何实现之前，先再次观察 在值 \(c\) 和 \(-c\) 处求一个多项式值之间的关系。 一般来说，我们可以写成 \(P_a(x) = E_a(x) + O_a(x)\)，其中 \(E_a\) 是偶幂次部分，\(O_a\) 是奇幂次部分。 也就是说，
快速多项式乘法的关键是找到正确的点来 用于求值／插值，以使这一过程高效。 特别是，我们要利用对称性，例如求值 \(x\) 和 \(-x\) 时所看到的对称性。 但这种对称性只够让我们用一半的时间处理选定的成对点， 所以只是省下了一个常数因子。 如果我们想做的不仅仅是把工作量减半， 就需要寻找点与点之间更多的对称性。 我们不仅要找到值对之间的对称性， 还要找到值对与值对之间、以及之后值对的值对之间 的更深层对称性。
回忆一下，复数 \(z\) 有一个实部和一个虚部。 如果我们用 \(y\) 维表示虚部，就可以把 \(z\) 在数轴上的位置考虑进来。 现在，如果满足以下条件，我们就把 \(z\) 定义为 n 次本原单位根：
\(z^n = 1\) 且
对 \(0 < k < n\)，\(z^k \neq 1\)。
\(z^0, z^1, ..., z^{n-1}\) 被称为 n 次单位根。 例如，当 \(n=4\) 时，\(z = i\)，因为 \(i^4 = 1\)。 下面这些恒等式对我们也有用： \(e^{i\pi} = -1\)，以及 \(z^j = e^{2\pi ij/n} = -1^{2j/n}\)。 其意义在于，我们可以在单位圆上找到任意多个 所需的点 （见图 26.7.1）。 而这些点之所以特殊，是因为它们让我们能够恰好完成 所需的计算，从而得到加速一次求多个点整体 过程所需的对称性。
现在我们想把上述思想变成一个具体的、详细的算法。 如果我们假设系数的个数是 2 的幂，这个过程会更容易理解 和实现，所以我们这样假设。 （我们总可以通过添加零值系数把多项式补齐到 合适的规模。）
定义一个 \(n \times n\) 矩阵 \(A_{z}\)，其第 \(i\) 行第 \(j\) 列的元素为
其思想是：每个根一行 （第 \(i\) 行对应 \(z^i\)），而每一列对应多项式 中 \(x\) 值的指数幂次。 例如，当 \(n = 4\) 时我们有 \(z = i\)。 于是，\(A_{z}\) 数组如下所示。
让 \(a = [a_0, a_1, ..., a_{n-1}]^T\) 成为一个向量，用于存储待评估的多项式系数。我们可以通过将 \(A_{z}\) 矩阵与系数向量相乘来计算多项式在第 \(n\) 个单位根上的值。结果向量 \(F_{z}\) 称为多项式的 离散傅里叶变换 ( DFT ) 值。请注意，我们还使用名称 \(b\) 来表示 \(F_z\) ，只是为了使下标表示更易于阅读。
我们还有两个问题。 我们需要能比标准的矩阵向量乘法更快地相乘这个 矩阵与向量，否则做求值仍然需要 \(n^2\) 次乘法。 即使我们能够廉价地相乘矩阵与向量， 我们仍然需要能够逆转这一过程。 也就是说，在通过求值变换两个输入多项式， 然后对求值点做逐对相乘之后，我们必须 对这些点插值，把对应原始输入多项式相乘结果的 多项式取回来。
我们先把第二个问题解决掉。 事实证明，插值步骤几乎与 求值步骤相同。
我们只需要求出 \(A_{z}^{-1}\)。 结果证明它很容易计算，定义如下。
换句话说，插值（逆变换）需要 与求值相同的计算，只是把 \(1/z\) 代入 \(z\) （最后还要乘上 \(1/n\)）。 所以，如果我们能快速完成其中一个步骤，就能快速完成 另一个步骤。
如果你考察 \(n=8\) 时示例 \(A_z\) 矩阵， 你应该会看到矩阵内部存在对称性。 例如，上半部分与下半部分相同，只是 某些行和列发生了合适符号变化。 左右两半也是如此。 存在一个高效的、以 \(\Theta(n \log n)\) 时间完成 求值和插值的分治算法。 这就是所谓的快速傅里叶变换。 它是一个分解矩阵乘法的递归函数， 利用了在 \(n\) 次单位根处求值所提供的对称性。
因此，使用傅里叶变换让多项式 \(A\) 和 \(B\) 相乘的完整过程如下。
把一个 \(n-1\) 次多项式表示为 \(2n-1\) 个系数：
\[[a_0, a_1, ..., a_{n-1}, 0, ..., 0]\]对 \(A\) 和 \(B\) 的表示执行傅里叶变换。
对结果做逐对相乘，得到 \(2n-1\) 个值。
执行逆傅里叶变换，得到 \(2n-1\) 次多项式 \(AB\)。
