对具有不同指数项的方程进行FFT

小编典典

对具有不同指数项的方程进行FFT

algorithm

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

阅读 262

2020-07-28

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

加零层的这样的载体是正确结果的大小（最大一个指数+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！因为n必须2提高 DFT 快速算法的性能，如果您还想提高性能，而不是查看 DFFT（A），DFFT（B） 的
DFFT 权重矩阵，它们是相同的，因此无需计算两次… *

2020-07-28