math - 使用 Vandermonde 矩阵的快速傅立叶变换 - 系数评估？

Question

假设我正在尝试评估多项式：

x^2 + 1

使用快速傅里叶变换方法评估系数。现在我可以使用 co-effcient 作为快速傅立叶变换的输入将其更改为矩阵/向量形式：

所以：

x^2 + 1 = <1, 0, 1, 0>

这是通过使用系数值来完成的，例如 1 = 1、0x^1 = 0、X^2 = 1 等等

现在我们到了我完全困惑的地方。我打算使用范德蒙德矩阵：范德蒙德矩阵〜维基使用矩阵将这些值评估为 FFT 形式：

1 1 1 1  
1 i-1-i
1-1 1-i
1-i 1 i

的输出

fft(1,0,1,0)

是

(2,0,2,0)

现在这就是我不太明白的步骤，我们如何使用该矩阵得到（2,0,2,0）？

score 3 · Accepted Answer

首先，您的 Vandermonde 矩阵不正确。(4,3) 条目应该是 -1，而不是 1，因为第四行应该是 (-i) ⁰ , (-i) ¹ , (-i) ² , (-i) ³。特别注意

(-i)*(-i) = (-1) ² * i ² = i ² = -1。

通过此校正，结果来自将 Vandermonde 矩阵乘以列向量 (1,0,1,0)。

score 2 · Accepted Answer

也许你可以在这里解释你的总体目标是什么。我从未听说过 FFT 用于评估多项式。它们用于多项式相乘或对信号进行卷积（等效任务），但除非多项式/信号具有大量项，否则我不会打扰。x ² + 1 不大。16 项并不大，甚至 64 或 256 项也可能通过简单的 O(N ² ) 技术更好地完成。

离散傅立叶变换使用矩阵 M _ij = ω ^ij其中 ω 是 1 的第 N 个复数根，列/行编号从 0 到 N-1。

快速傅立叶变换从不直接使用此矩阵，它们经过大量优化以使用分而治之的技术（Cooley-Tukey 算法）通过串联和并联的 2x2 DFT 阶段计算最终结果。

如果你把你的向量写成 [0,1,0,1] 而不是 [1,0,1,0]，我想你会看到如果你把它乘以你给出的矩阵，你会得到 [0, 2,0,2]。（虽然你有一个错误，它是

1 1 1 1  
1 i-1-i
1-1 1-1
1-i-1 i

) 您正在使用的程序中必须有一些约定，它可以反转向量系数的顺序。

2 回答 2