使用范德蒙矩阵进行快速傅立叶变换 - 系数评估？
假设我正在尝试评估多项式：
x^2 + 1
使用快速傅立叶变换方法来评估系数。 现在我可以使用系数作为快速傅里叶变换的输入将其更改为矩阵/向量形式：
所以：
x^2 + 1 = <1, 0, 1, 0>
这是通过使用系数值来完成的，例如 1 = 1、0x^1 = 0、X^2 = 1 和等等
现在我们到了我完全困惑的地方。 我打算使用范德蒙德矩阵：范德蒙德矩阵 ~ Wiki 将这些值评估为 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）？
Say i'm trying to evaluate the Polynomial:
x^2 + 1
Using the Fast Fourier transform method for evaluating co-efficients. Now i can change this into matrix/vector form using the co-effcient as inputs for the fast fourier transform:
so:
x^2 + 1 = <1, 0, 1, 0>
This is done by using the coefficient value e.g 1 = 1, 0x^1 = 0, X^2 = 1 and so on
Now we get to the bit where i'm totally confused. I'm meant to use the vandermonde matrix :Vandermonde matrix ~ Wiki to evaluate these values into FFT Form using the matrix:
1 1 1 1
1 i-1-i
1-1 1-i
1-i 1 i
The output of
fft(1,0,1,0)
is
(2,0,2,0)
Now thats the step i don't quite understand, how did we use that matrix to get (2,0,2,0)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
首先，您的范德蒙德矩阵不正确。 (4,3) 条目应该是 -1，而不是 1，因为第四行应该是 (-i)0、(-i)1、(-i )2、(-i)3。 请特别注意
(-i)*(-i) = (-1)2 * i2 = i2 = -1。
通过此校正，将 Vandermonde 矩阵乘以列向量 (1,0,1,0) 得出结果。
First, your Vandermonde matrix is incorrect. The (4,3) entry should be -1, not 1, since the fourth row should be (-i)0, (-i)1, (-i)2, (-i)3. Note in particular that
(-i)*(-i) = (-1)2 * i2 = i2 = -1.
With this correction, the result follows from multiplying the Vandermonde matrix by the column vector (1,0,1,0).
也许你可以在这里解释一下你的总体目标是什么。 我从未听说过使用 FFT 来计算多项式。 它们用于乘以多项式，或对信号进行卷积（等效任务），但除非多项式/信号具有大量项，否则我不会打扰。 x2 + 1 并不大。 16 项并不大，甚至 64 或 256 项也可能通过简单的 O(N2) 技术完成得更好。
离散傅里叶变换使用矩阵 Mij = ω< super>ij 其中 ω 是 1 的第 N 个复数根，列/行编号从 0 到 N-1。
快速傅立叶变换从不直接使用该矩阵，它们经过严格优化以使用分而治之技术（Cooley-Tukey 算法）通过串行和并行的 2x2 DFT 阶段计算最终结果。
如果你将向量写为 [0,1,0,1] 而不是 [1,0,1,0]，我想你会看到，如果你将其乘以你给出的矩阵，你会得到 [0, 2,0,2]。 （虽然你有一个错误，但它是
）你正在使用的程序中必须有一些约定来反转向量系数的顺序。
Maybe you could explain what your overall goal is here. I have never heard of FFTs being used to evaluate polynomials. They are used to multiply polynomials, or to convolve signals (an equivalent task), but I wouldn't bother unless the polynomials/signals have a large number of terms. x2 + 1 isn't large. 16 terms is not large, and even 64 or 256 terms is probably better done by straightforward O(N2) techniques.
Discrete Fourier Transforms use the matrix Mij = ωij where ω is the Nth complex root of 1 and column/row numbering goes from 0 to N-1.
Fast Fourier Transforms never use this matrix directly, they are heavily optimized to use a divide-and-conquer technique (Cooley-Tukey algorithm) to calculate the end result through stages of 2x2 DFTs in series and parallel.
If you write your vector as [0,1,0,1] instead of [1,0,1,0], I think you will see that if you multiply that by the matrix you gave, you'll get [0,2,0,2]. (Although you have an error, it's
) There must be some convention in the program you are using which reverses the order of the vector's coefficients.