math - 快速傅里叶变换多项式评估的“树”？

Question

我正在尝试通过使用 FFT 的分治算法来评估多项式 A(x)。我基本上将多项式分解为奇数根和偶数根，然后在两个较小的多项式上递归。（允许我每次递归计算两倍的数值）。

为了可视化这一点，我试图创建一棵树来显示多项式在算法中的路径。我不确定如何开始——有人可以让我开始吗？我不期望一棵完整的树只是一个让我走上正确道路的简短示例。

Answer 1

这是算法第 2 章中的一个简单示例：

A(x) = 3 + 4x + 6x^2 + 2x^3 + x^4 + 10x^5
     = (3 + 6x^2 + x^4) + x(4 + 2x^2 + 10x^4)
     = E(x^2) + x*O(x^2)

在哪里

E(x) = 3 + 6x + x^2
O(x) = 4 + 2x + 10x^2

请注意多项式的大小如何缩小了 2 倍？x此外，我们可以在因为-x将产生相似的值时循环评估。

A(x) = E(x^2) + x*O(x^2)
A(-x) = E(x^2) - x*O(x^2)

我希望你能看到这个递归过程是如何变成一棵树的。