約 2,448,743 件
https://w.atwiki.jp/amaeda/pages/53.html
FFTWマニュアル - FFTWリファレンス - データタイプとファイル - メモリ確保 メモリ確保 Memory Allocation void *fftw_malloc( size_t n ); void fftw_free( void *p ); これらは、mallocやfreeとほとんど同じ働きを持ちます。唯一、返り値のポインタがFFTWのすべてのアルゴリズム(例えばSIMD高速化)に必要な制約を満たすこちだけがことなります。3.1節のデータの並びも参照のこと。 fftw_mallocで確保されたメモリは、通常のfreeではなく、fftw_freeで解放しなければいけません。 これらのルーチンは、ただ単にユーザーのOSのmallocを呼び出し、必要であればメモリ配置がそろった同等の関数を呼びます(memalignなど)。したがって、通常は時間や空間のオーバーヘッドが著しく生じる心配はありません。また、データを確保するのに必ずしもこの関数を呼び出す必要はありませんが、この方法を強く推奨します。 記 C++では、通常のmallocと同様に、fftw_mallocの出力を確保する型にキャストする必要があります。
https://w.atwiki.jp/amaeda/pages/32.html
実データ多次元離散フーリエ変換 Multi-Dimensional DFTs of Real Data 実データの多次元離散フーリエ変換は、以下のプランナールーチンを使います。 fftw_plan fftw_plan_dft_r2c_2d( int nx, int ny, double *in, fftw_complex *out, unsigned flag ); fftw_plan fftw_plan_dft_r2c_3d( int nx, int ny, int nz, double *in, fftw_complex *out, unsigned flag ); fftw_plan fftw_plan_dft_r2c( int rank, const int *n, double *in, fftw_complex *out, unsigned flag ); 対応するc2rルーチンは、それぞれ入出力の型が入れ替わるだけです。 これらのルーチンは、複素数の出力配列が、だいたい半分になり、入出力が同じin-place変換を行う場合、実配列に余白が必要なこと以外は、複素数の場合と同様に働きます。(1dの場合と同様です) 前述のとおり、nは配列の論理サイズで、複素配列の様式は非常に注意が必要です。実データが、行メジャー順で、n1 x n2 x n3 x・・・x ndの次元だった時を考えます。すると、r2c変換の後に出力は、行メジャー順で、n1 x n2 x n3 x・・・x(nd/2 + 1)のfftw_complexの配列で、対応する複素数離散フーリエ変換の出力の半分のサイズをわずかに上回るサイズになります。(割り算は切り捨てです)一方で、データの並びは、複素数離散フーリエ変換の場合とまったく同じになります。 複素数データは、実データよりわずかに大きいため、入出力が同じin-place変換では、いくつか複雑な問題が生じます。この場合ですと、実データの最後の次元は、複素数データを格納するために、余白が必要となります。余白の大きさは、最後の次元が偶数か奇数かによって変わります。つまり、実データの最後の次元は、物理的に2(nd/2 + 1)個のdoubleの大きさをもちます(複素数データをちょうど格納できる大きさです)。この物理的配列サイズは、論理的配列サイズを変えることはありません。すなわち、ndの値のみが実際に最後の次元に格納され、プラン生成のルーチンに引数として渡されます。 たとえば、nx x nyの２次元実配列の変換を考えてみましょう。r2c変換の出力は、nx x (ny/2 + 1)の２次元複素配列になり、yの次元は出力の冗長性により、およそ半分のサイズになっています。fftw_complexは、doubleの２倍の大きさであるため、出力配列は入力配列よりわずかに大きくなります。 このようにして、もし入出力が同じ変換を計算したい場合、入力配列の大きさが、nx x 2(ny/2 + 1)の大きさになるように、余白を設けなければなりません。 nyが偶数であれば、各列の最後に余白は２つになります(この余白は出力用に使われるだけなので、初期化は必要ありません)。 以下のイラストは、今述べた入出力配列を表わしていて、in-place変換、out-of-place変換両者が示されています(矢印は、連続するメモリ領域を示しています)。 (fftw3マニュアルより抜粋) これらの変換は、正規化されていないので、c2r変換に引き続いてr2c変換を行うと(あるいはその逆でも)、元のデータがデータ数(実データの論理次元の積)倍された結果になります。 最後の次元は、特別に扱われてるため、最後の次元を１とした場合は、低い次元のr2c/c2r変換と等価にはなりません。この場合は、最後の複素数の次元は、サイズ１になり、いかなる利点も生まれません。
https://w.atwiki.jp/amaeda/pages/41.html
FFTWマニュアル - その他重要なこと - 多次元配列のフォーマット - 行メジャー形式 行メジャー形式 Row-major Format fftw_plan_dftなどにわたされる多次元配列は、単一の連続するブロックに列メジャー順(C順序と呼ばれることもある)で格納されています。基本的には、これはメモリの隣の場所に移れば、最初の次元の添え字が最も遅く変化し、最後の次元の添え字がもっともはやく変化することを意味します。 もっと具体的に言うと、rank dのn1 x n2 x n3 x・・・xndの配列を考えたとします。そして、配列の場所をゼロベースの添え字で特定すれば、(i1, i2, i3, ・・・,id)となります。もし、配列が行メジャー順であれば、この要素は、id + nd(id-1 + nd-1(・・・+n2i1))の場所に相当します。 通常の複素離散フーリエ変換に対しては、配列の各要素は、fftw_complex型でなければなりません。つまり、数(double精度)のペア(実部、虚部)です。 アドバンストFFTWインターフェイスでは、物理的次元nの添え字は、論理次元より大きく、別個に計算されます。これは、より大きな配列の一部を変換するためです。そして、アドバンストインターフェースでは、上記のものは実際の配列サイズを得るために、ストライド(stride)が掛っています。これは、多次元配列の各要素が実際のデータ構造になっていて、ひとつの場所だけ変換したい場合に便利です。これに対し、ベーシックインターフェースでは、ストライド(stride)は１になっています。
https://w.atwiki.jp/amaeda/pages/54.html
FFTWマニュアル - FFTWリファレンス - プランの利用 プランの利用 Using Plans FFTWにおけるすべての変換のプランは、fftw_plan型として(不透明なポインタ型)格納され、これからの節で述べる様々なルーチンによって生成されます。fftw_planは、変換を計算するのに必要なすべての情報を持っていて、たとえば入出力配列のポインタなどもそれに含まれます。 void fftw_execute( const fftw_plan plan ); 上記によってプランが実行され、あらかじめ計画された配列に対する変換が計算されます(その配列はこの時、存在する必要があります)。プランに変更がなければ、fftw_executeは所望の回数だけ実行することができます。 既にあるプランを、違う配列に使いたいときは、グルインターフェースを使うことができます。これについては、4.5節のグルインターフェースを参照のこと。 fftw_execute(と同等の関数)は、FFTWがスレッドセーフであることを保証した唯一の関数です。これについては、5.2節のスレッドの安全性を参照のこと。 次の void fftw_destroy_plan( fftw_plan plan ); は、プランと関連するデータを解放します。 FFTWのプランナーは、いくつかの持続性のあるデータをセーブしています。たとえば、蓄積されたwisdom(知)や、現在の設定で利用できるアルゴリズムの一覧などです。もしこれら全てを解放し、FFTWをプログラムを立ち上げたときの最初の状態に戻したい場合、 void fftw_cleanup( void ); を呼び出してください。 fftw_cleanupを呼び出したあとには、すべての現存するプランが未定義となり、プランを実行(execute)することも、破棄(destroy)することもすべきでありません。しかし、新しいプランに関しては、生成、実行/破棄することができて、FFTWは知(wisdom)の情報の蓄積が再び始まります。 fftw_cleanupは、プランを解放しません。したがって、解放の目的でfftw_destroy_planを呼ぶ必要があります。 ※この近辺は主張が矛盾しているようでよくわからない 次の二つのルーチンは、純粋な学問上の目的で作られています。 void fftw_flops( const fftw_plan plan, double *add, double *mul, double *fma ); plangが与えられた時、addとmulとfmaを、プランの実行に必要な、浮動小数点の加算、乗算、加算と乗算の組み合わせの正確な演算回数にセットします。 この浮動小数点の演算総演算回数(flops)は、add+mul+2*fmaかadd+mul+fmaになります(後者は、ハードウェアが加算乗算の組み合わせ演算命令をサポートしている場合です。また、FMA演算の回数はvoodooコンパイラによってのみ最適。演算回数は整数でなければならないが、大きな変換を行った時のintのオーバーフローを避けるためにdoubleを使用していて、単精度、４倍精度FFTWでも引数はdouble型です。) void fftw_fprint_plan( cost fftw_plan plan, FILE *output_file ); void fftw_print_plan( const fftw_plan plan ); 上記関数は、"マニアなら読める"書式で、プランを入力のファイルあるいはstdout(標準出力)にそれぞれ出力します。
https://w.atwiki.jp/amaeda/pages/47.html
FFTWマニュアル - その他重要なこと - 知の利用-プランの保存 知の利用-プランの保存 Words of Wisdom - Saving Plans FFTWは、プランを保存したり、保存してあるプランを復元したりする方法を実装しています。実際のところは、FFTWがやっていることは、プランを保存して読み込むというだけでなく、もっと一般的なことをやっています。そのメカニズムは、”wisdom(知)”と呼ばれます。ここでは、この特徴を大雑把に説明します。詳細は、４章のFFTW Referenceの21ページを見てください。ここには、FFTWでwisdomをどう利用するかについて、より難しくなりますが、細かいところまで完全に議論が展開されています。 FFTW_MEASURE,FFTW_PATIENT,FFTW_EXHAUSTIVEオプションで生成されたプランは、最適に近いFFTのパフォーマンスを実現しますが、FFTWは多数の考えうるプランの実行時間を計り、最適なものを選ばなければいけないので、長時間かかるかもしれません。この設定は、同サイズの多数の変換を計算しなくてはいけなくて、最初の計算の時間は無視できるような場合のためにあります。初期化時間を短くするためには、変換が遅くなりますが、FFTW_ESTIMATEというものを用意してあります。wisdomのメカニズムは、(初期化時間も短く、変換も速いという意味で)両者の良い所をとっていることになります。つまり、良いプランを一度計算し、それをに保存して、後で必要なだけ読み込みます。wisdomメカニズムは、実際には多くのプランを一度に保存したり、読み込んだりしますが、それだけではありません。 プランを作るときにはいつも、FFTWプランナーはwisdomを蓄積します。このwisdomは、プランを再構成するのに十分な情報を持っています。プランを立て終わった後、この情報は以下の関数で保存できます。 void fftw_export_wisdom_to_file( FILE *output_file ); 次の機会に、プログラムを走らせるときには、wisdomをfftw_import_wisdom_from_fileで復元でき(成功すれば、ノンゼロの値が返ってきます)、以前と同じフラグをつかって、プランを再生成することができます。 int fftw_import_wisdom_from_file( FILE *input_file ); wisdomは、自動的に利用可能なものに対して有効です。つまり、プランナーのフラグがwisdomが生成したプランより”patient”でなかった場合です。たとえば、FFTW_MEASUREで生成されたwisdomは、FFTW_ESTIMATEやFFTW_MEASUREに対し、保存されたものを再利用することができますが、FFTW_PATIENTに対しては使えません。 このwisdomは、どんどん蓄積されていくもので、FFTWのグローバルで、プライベートな内部データ構造に格納されます。格納サイズは最小限で、wisdomが生成されるデータサイズの対数に比例します。もし、メモリの利用が心配であれば、wisdomとそれに関連するメモリは、次の関数で解放されます void fftw_forget_wisdom( void ); wisdomは、ファイルや、文字列や、他のものにも保存することができます。 詳細は37ページ,4.6章のWisdomを参照してください。
https://w.atwiki.jp/amaeda/pages/48.html
FFTWマニュアル - その他重要なこと - 知の利用上の注意-Caveats in Using Wisdom 知の利用上の注意 Caveats in Using Wisdom 實に， 知惠が 多くなれば 惱みも 多くなり， 知識を 增す 者は 悲しみを 增す．[Ecclesiates 1 18] wisdomの利用には落とし穴があります。それはFFTWのハードウェアやその他の条件への適応能力を、無意味なものにしてしまいうることです。例えば、あるプロセッサで稼働するプログラムから、wisdomを外部へ出力し、他のプロセッサーで稼動するプログラムに取り込むなどという状況は、十分に想定されます。これを行うと、２番目のプログラムは、そのマシンの最適なプランではなく、１番目のプロセッサで最適化されたプランを使うことを意味します。 wisdomは、ハードウェアとプログラムのバイナリが変わらない限り安全に再利用できるはずです（実際には、同じハードウェア/プログラムバイナリであっても、仮想メモリやその他の条件の違いによって、最適なプランは変わっているかもしれません。パフォーマンスに特に関心があるユーザーは、この点に注意する必要があります。）同じwisdomが２つのバイナリで使われた時、それが同じマシン上であったとしても、プランはコードの並びの違いによって準最適になるということは、大いにありうることです。したがって、wisdomはアプリケーションが再コンパイルされるごとに、再生成するのが賢いといえます。利用する時と、使う時の、ハード/ソフトの変更が大きくなれがなるほど、準最適なプランを利用するリスクは高くなります。 とはいえ、プラン生成の選択がFFTW_ESTIMATEか、恐らく準最適なwisdom（同じマシン、違うバイナリで生成された）の間の選択をする時には、wisdomを使うことで性能は向上する傾向にあります。こんなわけで、我々は標準的な幅広いシステムに対応する場所(Unixでは,/etc/fftw/wisdom)から、以下の、wisdomを取り込む関数を提供しています。 int fftw_import_system_wisdom( void ); FFTWは、単独で動作するfftw-wisdom（Unixのman参照）というプログラムも提供していて、それを使うとユーザは、システムのwisdomファイルに格納されている、標準的なサイズセットのwisdomを作れます。詳しくは、39ページ、4.6.4節のWisdom Utiltiesを参照のこと。
https://w.atwiki.jp/amaeda/pages/46.html
FFTWマニュアル - その他重要なこと - 多次元配列のフォーマット - C言語における動的配列(間違えた使い方) C言語における動的配列(間違えた使い方) Dynamic Arrays in C - The Wrong Way C言語で多次元配列のメモリ確保に用いられる他の方法は、しばしばFFTWで利用できません。これを行うと、FFTWで深刻なエラーがおきるかもしれません。ここではその方法は、よく知られ使われているため、これについて議論します。この方法は、配列のポインタの配列のポインタの・・・を作るものです。たとえば、以下のようなものです。 int i,j; fftw_complex ***a_bad_array; /* 5x12x27の配列を確保する他の方法 */ a_bad_array = (fftw_complex***)malloc( 5 * sizeof(fftw_complex**) ); for( i=0; i 5; ++i ){ a_bad_array[i] = (fftw_complex**)malloc( 12 * sizeof(fftw_complex*) ); for( j=0; j 12; ++j ) a_bad_array[i][j] = (fftw_complex*)malloc( 27 * sizeof(fftw_complex) ); } ご存じのとおりこの種の配列は確保するのも(解放するのも)大変です。一方で、(i.j,k)番目の要素が、a_bad_array[i][j][k]というように簡単に参照できる利点があります。 もしこの方法が好きで、配列へのアクセスを最大限に簡単にしたい要望があり、さらにFFTWに配列を渡したい場合は、両者の特性を生かしたハイブリッドメソッドを使うことができます。配列を1つの連続したブロックで確保して、同時にポインタ配列の配列もブロックの適切な場所で宣言します。この種のテクニックは、このドキュメントの範囲を超えているので、C言語の多次元配列の情報をもっと得たい場合は、comp.lang.cのFAQを参照してください。
https://w.atwiki.jp/amaeda/pages/39.html
FFTWマニュアル - その他重要なこと - データの並び データの並び Data Alignment FFTWで最高のパフォーマンスを得るためには、x86(Pentia)アーキテクチャにおける２つの問題についていくらか知っておく必要があります。 (SIMD高速化用に使われる)確保されたメモリの並び、スタックの並びです。 SIMDの並びとfftw_malloc x86アーキテクチャにおけるスタックの並び
https://w.atwiki.jp/amaeda/pages/51.html
FFTWマニュアル - FFTWリファレンス - データタイプとファイル - 複素数 複素数の取扱 Complex numbers FFTWのインターフェースは、すべての浮動小数点数に、double精度を用いており、複素数を保持するfftw_complex型を以下のように定義しています typedef double fftw_complex[2]; ここで、[0]の要素は実部、[1]の要素は虚部をそれぞれ表しています。 代替手段として、(gccのような)ANSI C標準のC99をサポートするＣコンパイラがあれば、C言語の新しいネイティブな複素数型(バイナリとしては、上の型と同じ)も使うことができます。すなわち、#include complex.h を fftw3.h の前にインクルードすれば、fftw_complexが、ネイティブの複素数型として定義され、通常の数学で扱うことができるようになります(たとえば、x = y * (3+4*I)のように。xとyはfftw_complexでIは単位虚数記号)。 以下、作業中。細かい話なので後回しにする予定 C++は、自身でcomplex T というテンプレートクラスを持っており、これは標準ヘッダである complex で定義されています。伝えられるところによれば、C++標準委員会は、最近
https://w.atwiki.jp/amaeda/pages/50.html
FFTWマニュアル - FFTWリファレンス - データタイプとファイル データタイプとファイル Data Types and Files FFTWを利用したすべてのファイルは、以下のヘッダファイルをインクルードする必要があります。 #include fftw3.h また、FFTWライブラリへのリンクも必要です。Unixでは、 -lfftw3 -lm オプションを、リンクコマンドの最後に付け加えればよいです。 複素数 精度 メモリ確保