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

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))

相当于卷积（适当填充）。 卷积可以解释为两个多项式的乘法。 去查找卷积的定义（非常简单）并在纸上手工算出来。 我希望它能为您带来很多启发......

保罗
中心空间软件