2

我是 FFT 的新手，所以我对一些概念有些困惑。到目前为止，我看到的方程乘法的 FFT 示例涉及具有连续指数（即A(x) = 1 + 3x + 5x^2 +...和）B(x) = 4 + 6x + 9x^2 + ...的方程C(x) = A(x)*B(x)。但是，是否可以在两个指数不相等的方程上使用 FFT？例如，是否可以使用 FFT 进行乘法：

A(x) = 1 + 3x^2 + 9x^8

和

B(x) = 5x + 6 x^3 + 10x^8

及时O(nlogn)？

如果没有，是否有运行时的情况O(nlogn)？例如，如果产品中的术语数O(n)不是O(n^2)？

即使运行时间超过O(nlogn)，我们如何使用 FFT 来最小化运行时间？

4

1 回答 1

0

是的，可以在不等指数多项式上使用DFFT ...

丢失的指数只是乘以0它也是一个数字......只需重写你的多项式：

A(x) = 1 + 3x^2 + 9x^8
B(x) = 5x + 6x^3 + 10x^8

像这样：

A(x) = 1x^0 + 0x^1 + 3x^2 + 0x^3 + 0x^4+ 0x^5+ 0x^6+ 0x^7 +  9x^8
B(x) = 0x^0 + 5x^1 + 0x^2 + 6x^3 + 0x^4+ 0x^5+ 0x^6+ 0x^7 + 10x^8

所以你的DFFT向量是：

A = (1,0,3,0,0,0,0,0, 9)
B = (0,5,0,6,0,0,0,0,10)

添加零，因此向量是正确的结果大小（最大 A 指数 +1 + 最大 B 指数 +1）并且还向上舍入到最接近的幂以2用于DFFT，因此原始大小为9,9 -> 9+9 -> 18 -> round up -> 32

A = (1,0,3,0,0,0,0,0, 9,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0)
B = (0,5,0,6,0,0,0,0,10,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0)
//  |    original      | correct result  |    nearest power of 2      |

并做你想要的DFFT的东西......我假设你想做这样的事情：

A' = DFFT(A)
B' = DFFT(B)
C(i)' = A'(i) * B'(i)   // i=0..n-1
C= IDFFT(C')

这是O(n*log(n))。不要忘记，如果您使用DFFT（不是 DFT）n = 32而不是 18 ！！！因为如果您想要提高性能而不是查看DFFT(A)、DFFT(B)的DFFT权重矩阵，则n必须是DFT2快速算法的强大功能，因此它们是相同的，因此无需计算两次...

于 2014-03-18T09:17:47.450 回答