algorithm - 快速傅里叶变换多项式乘法？

Question

我正在使用 FFT 在某些点评估多项式，以便可以使用值表示法来表示它。 (表示为与其度数相等的点数)

然而，要将两个 d 次多项式相乘，我需要在 2d + 1 个点上计算两者。然而，使用 FFT 进行评估(乘以 d 次单位根)仅评估 d 点处的多项式。因此，如果仅在 d 点评估多项式，FFT 如何用于评估多项式评估？ (与 2d + 1 相反)

Answer 1

您可以选择您评估的 -1 的第 n 个方根。如果您需要 2d-1 个点(正如我怀疑的那样)，只需使用 -1 的第 (2d-1) 个根。事实上，您通常会使用 -1 的 2^k 次方根，其中 2^k 是 2 >= 2d-1 的第一个幂，因为对于 2 的幂更容易获得快速 FFT。复杂性仍然是 O(d log d)，因为 O 的定义允许常数因子。