fft - 快速傅里叶变换 - 多项式相乘？

Question

我只是不明白如何对两个多项式（例如 X^2+1 和 X+1）执行 FFT ......有人可以和我一起一步一步地完成这个过程吗？

非常感谢

Answer 1

只需使用您的多项式系数作为 fft 的输入：

octave:16> poly1=[1 0 1 0]
poly1 =

   1   0   1   0

注意：这意味着 x^2+1

octave:17> poly2=[1 1 0 0]
poly2 =

   1   1   0   0

octave:18> ifft( fft(poly1).*fft(poly2))
ans =

   1   1   1   1

这就是结果。解释为x^3+x^2+x+1，是两个多项式的乘积。

Answer 2

但实际上这里发生的是卷积。

ifft(fft(poly1).*fft(poly2))

相当于卷积（适当填充）。而卷积可以解释为两个多项式的乘法。去查一下卷积的定义（很简单），在纸上手工算出来。我希望它会为您提供很多关于这方面的信息......

保罗
中心空间软件