algorithm - 具有不同指数项的方程式的 FFT

Question

我是 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 来最小化运行时间？

Answer 1

是的，可以对非等指数多项式使用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)，并为 DFFT2 的幂> 原始大小为 9,9 -> 9+9 -> 18 -> 向上舍入 -> 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!因为 n 必须是 2 的幂才能实现 DFT 的快速算法，如果您想要提高性能而不是查看 DFFT> DFFT(A),DFFT(B) 的权重矩阵它们是相同的所以不需要计算它们两次 ...