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

Question

我正在使用 FFT 在某些点评估多项式，以便可以使用值表示来表示它。（表示为等于其度数的点数）

但是，要将两个 d 次多项式相乘，我需要在 2d + 1 个点处同时评估这两个多项式。然而，使用 FFT 进行评估（乘以第 d 个单位根）仅评估 d 点处的多项式。因此，如果 FFT 仅在 d 点评估多项式，它如何用于评估多项式评估？（相对于 2d + 1）

Answer 1

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