DiscreteTransforms パッケージのFourierTransform と InverseFourierTransformの効率的な利用
|
説明
|
|
|
N データ点について使用され、N[i]<N[i+1] として、N = N[1] N[2] ... N[m] の素因数をもつ場合、FFT アルゴリズムは、(非常に) 粗い近似では、計算量は、N x N[m] x log(N)/log(N[m]) に比例します。DFT (離散フーリエ変換 ) アルゴリズムは、単純にN^2 の計算量 をもちます。 (algorithm=DFT オプションの詳細は、 DiscreteTransforms[FourierTransform] を参照してください。)
|
|
FFT アルゴリズムの計算量は、データの長さの因数分解に強く依存しますが、 DFT アルゴリズムの計算量 の場合は、そうではありません。 N が素数の場合、両方のアルゴリズムの計算量は、ほぼ同じです。
|
•
|
FFT アルゴリズム の効率が最も良くなるケースは、データの長さが 2 のベキ乗である場合に起こります。この場合、 FFT 計算量 は、N x log(N) に比例し、これは、DFT アルゴリズムの N^2 の計算量に匹敵します。 改良に関する非常に重要な要素です。
|
•
|
FourierTransform と InverseFourierTransform コマンドは、より適切なデータ長を得るために 入力データを0(ゼロ)埋めするpadding オプションを与えます。 しかし、これは、変換の高周波部分を歪ませるため、 必ずしも望ましくありません(そのため、これはオプションとして提供されます)。
|
•
|
時間の効率に加え、メモリ量もまた、大きいデータ配列を取り扱う際に注意すべきこととなります。ここで第1に考慮すべきことは、入力データが、datatype=complex[8] をもつ、1つの配列 (あるいは ベクトル または 行列) の形で与えられる必要があるということです。というのは、これがアルゴリズムの実現で使用されるデータ型であり、inplace=true を指定する必要があるためです。 異なるデータ型 (たとえば、2つの float[8] 配列、あるいは、1つの complex 配列) が使用される場合、入力は、 complex[8] データタイプに変換されます。これは、入力データ用に必要なメモリ量を事実上、倍にします。
|
•
|
合成数のデータ長に対して、minstorage FFT アルゴリズムは、フーリエ変換を計算するための必要なメモリ量が最小になります。(inplace=trueにより)in-placeが行われることを仮定して、入力データ (出力データにもあてはまります)に加えて、データ長の最大素数のサイズの2倍の複素数用のメモリが追加で必要です。
|
|
対照的に(再び合成数データ長に対して)、mintimeアルゴリズムは、計算されるどの単一の変換の最大のサイズ(1つの1-D変換に対して、これは、単にデータの長さです)、あるいは、データ長で最大の素数の2倍のどちらがより大きいか計算され、複素数用のメモリが追加で必要になります。
|
|
これは、大きいデータセットに対して非常に重要になります。
|
|
注意: 一般に、mintime アルゴリズムの実行時間は、常に minstorage アルゴリズムの実行時間より少ないか、等しくなります。
|
•
|
データの長さが素数である場合、DFT アルゴリズムでは、入力データ長の高々1.5倍の最小の追加メモリ量を必要とします。 (これは、データの長さが素数である場合、mintime と minstorage アルゴリズムよりも25% 少なくなります)。 しかし、変換が素数の長さをもち、 メモリの使用が問題になるほど大きい場合、DFTの計算には、非常に長い時間がかかります。
|
•
|
メモリスペースを効率的に使用するための決定的に重要なこととして、 padding が使用されても、メモリスペースに注目する必要がない場合、padding はデータ配列を希望するpaddedサイズに割り当て、さらに、残りの要素すべてを零と置き(つまり、padding をマニュアルで行い)、データ値をもつ最初の要素のみを移動することにより、マニュアルで行われる必要があります。
|
|
ガイドライン
|
|
|
FourierTransform および InverseFourierTransform コマンドが時間とメモリを効率的に使用するためには、つぎのガイドラインに従ってください。
|
|
1. 常に、高度合成数となるデータ点数を使用してください (最適にするには、すべての因数が 2~5の間にある必要があります)。
|
|
2. 入力データの長さが高度合成数でない場合、入力データ配列を作成する際にマニュアルで padding を実行してください。
|
|
3. 常に datatype=complex[8] を使用し、inplace=true により inplace の操作を使用してください。
|
|
4. 時間を短縮したい場合には、algorithm=mintime を使用してください。一方、使用するメモリ量をより少なくしたい場合には、algorithm=minstorage を使用してください。
|
|
|
|
例
|
|
>
|
with(DiscreteTransforms);
|
| (2.1) |
データの長さ 1000000 をもつ問題を考えます。 複素数データ のみの保存には、16 MBが必要です。minstorage アルゴリズムの使用には、実際に追加のデータ が割り当てられないこと (最大の素因数が5であること)が必要です。 一方、この場合、(デフォルトの) mintime アルゴリズムの使用は、さらに16 MB の割り当てが必要です。
注意: 入力データセットをより高速に構成するためには、ArrayTools と evalhf を使用してください (これは、i=1..Nに対して sqrt(i/N)+I*sin(10*i/N) です )。
>
|
N := 1000000:
Z := Vector(N,datatype=complex[8]):
Za := ArrayTools:-ComplexAsFloat(Z):
fill := proc(N,Za) local i;
for i to N do
Za[2*i-1] := sqrt(i/N);
Za[2*i] := sin(10*i/N);
end do:
end proc:
evalhf(fill(N,var(Za))):
|
さらに、この時点でMapleのメモリ使用量は、~ 17MB - データ配列のサイズ です。
'minstorage'を使用した変換:
>
|
tt := time():
FourierTransform(Z, inplace=true, algorithm=minstorage):
time()-tt;
|
| (2.2) |
また、Maple のメモリ使用量は、ほぼ一定に留まります。
つぎは、デフォルトの 'mintime' 変換 (Zを再設定後)です。
>
|
evalhf(fill(N,var(Za))):
|
>
|
tt := time():
FourierTransform(Z, inplace=true, algorithm=mintime):
time()-tt;
|
| (2.3) |
この場合、問題に対して処理時間は大幅に少なくて済みますが、 Mapleのメモリ使用量を ~ 32 MB (2倍)程度に増やします。
|
|
Download Help Document
Was this information helpful?