• ベストアンサー

多次元高速フーリエ変換について

高速フーリエ変換fftによって、計算量のオーダーが n^2 からnlogn まで落とせるんですよね? それで、3次元のフーリエ変換って、 1次元のフーリエ変換を3回やれば n^2*nlogn=n^3lognのオーダーでできると思うのですが、 これ以上速いオーダーではできませんか?

質問者が選んだベストアンサー

  • ベストアンサー
  • tatsumi01
  • ベストアンサー率30% (976/3185)
回答No.1

無理だと思います。 対称性の利用などで、さらに1/2倍とか1/4倍にはできますが。 あと、WFTA というものがあったと記憶しているので調べてください。 WFTA (Winograd Transform Algorithm)

関連するQ&A