編集履歴

回答編集履歴

追記

2016/11/12 15:30

投稿

スコア4352

test CHANGED Viewed

@@ -12,7 +12,11 @@
 「2次元化FFT」というのは正式な呼び名ではないかもしれません。「six-step FFT」のほうがウェブ検索でよくヒットします。詳しい解説としては、たとえば計算物質科学イニシアティブでの2014年の講義「[大規模系での高速フーリエ変換1](http://www.cms-initiative.jp/ja/research-support/develop-support/how-to-publish/develop-apps/apps-implement/2014-haishinB-06)」などはどうでしょう。「n=n1n2に対するFFTアルゴリズム」のところからです。
-簡単に言うと、N = n1・n2個のサンプルをn1 × n2の2次元に配列し直し、n1個の行とn2個の列のそれぞれでFFTを実行し、それらn1 + n2回のFFTの結果からN個の場合のFFTの結果を計算する、という手法です。計算の各ステップでは、n1個またはn2個のデータだけがメモリ上にあればいいことになります。
+簡単に言うと、N = n1・n2個のサンプルをn1 × n2の2次元に配列し直し、n1個の行とn2個の列のそれぞれで1次元FFTを実行し、それら2・n1・n2回のFFTの結果からN個の場合のFFTの結果を計算する、という手法です。計算の各ステップでは、n1個またはn2個のデータだけがメモリ上にあればいいことになります。必要ないデータは外部記憶に書き出し、必要になったら読み込みます。
 上記の講義でも述べているように、もともとこの手法は、FFTのサンプル数がCPUの[キャッシュメモリ](https://ja.wikipedia.org/wiki/L2%E3%82%AD%E3%83%A3%E3%83%83%E3%82%B7%E3%83%A5)のサイズと比較して大きいと、キャッシュミスが多発して処理速度が著しく低下する、ということへの対策として考えられたようです。しかし今回の場合は、メインメモリをディスクに、キャッシュメモリをメインメモリに置きかえて考えてみて下さい。
+(11/12さらに追記。また前回追記分で式がおかしいところを直しました)
+ともかく、この手法は1次元FFTについて計算の各ステップで必要なメモリを節約しているだけで、4次元分の計算が必要なことは変わりません。でも、1次元分だけに適用して他の次元は全範囲をメモリに置くとしても、回答冒頭の例では必要メモリ量が`2**5 * 2**10**3 * 2 = 2**36`バイトに減らせます。かなり現実的な数字になってきますね。

six-step FFTの情報を追記

2016/11/12 15:30

投稿

ikedas

スコア4352

test CHANGED Viewed

@@ -6,3 +6,13 @@
 こういったマイナス要因があってもなお、許容できる時間内で結果が出せそうであれば、試す価値はあると思います。
+---
+(追記)
+「2次元化FFT」というのは正式な呼び名ではないかもしれません。「six-step FFT」のほうがウェブ検索でよくヒットします。詳しい解説としては、たとえば計算物質科学イニシアティブでの2014年の講義「[大規模系での高速フーリエ変換1](http://www.cms-initiative.jp/ja/research-support/develop-support/how-to-publish/develop-apps/apps-implement/2014-haishinB-06)」などはどうでしょう。「n=n1n2に対するFFTアルゴリズム」のところからです。
+簡単に言うと、N = n1・n2個のサンプルをn1 × n2の2次元に配列し直し、n1個の行とn2個の列のそれぞれでFFTを実行し、それらn1 + n2回のFFTの結果からN個の場合のFFTの結果を計算する、という手法です。計算の各ステップでは、n1個またはn2個のデータだけがメモリ上にあればいいことになります。
+上記の講義でも述べているように、もともとこの手法は、FFTのサンプル数がCPUの[キャッシュメモリ](https://ja.wikipedia.org/wiki/L2%E3%82%AD%E3%83%A3%E3%83%83%E3%82%B7%E3%83%A5)のサイズと比較して大きいと、キャッシュミスが多発して処理速度が著しく低下する、ということへの対策として考えられたようです。しかし今回の場合は、メインメモリをディスクに、キャッシュメモリをメインメモリに置きかえて考えてみて下さい。