2

私はFFTを初めて使用するので、いくつかの概念について少し混乱しています。これまで私が見た方程式の乗算の FFT の例には、指数が連続する方程式 (つまりA(x) = 1 + 3x + 5x^2 +...とB(x) = 4 + 6x + 9x^2 + ...とC(x) = A(x)*B(x)) が含まれていました。ただし、指数が等しくない 2 つの方程式で 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) になるようにゼロを追加し、 DFFT2を使用するために の最も近い累乗に切り上げると、元のサイズは次のようになります。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 = 18 ではなく 32であることを忘れないでください!!! DFFT（A）、DFFT（B）のDFFT重み行列を見るよりもパフォーマンスを向上させたい場合も、 DFTの高速アルゴリズムのべき乗でなければならないため、それらは同じであるため、2回計算する必要はありません...n2

于 2014-03-18T09:17:47.450 に答える