FFTWを使った畳み込み積分の高速化

目的

無限区間で定義された次の畳み込み積分

を数値的に計算することを考えよう。関数 f(x), g(x) は x=0 の近くに局在している関数として、計算区間としては対称的な区間 -W/2<x<W/2 を取りたいとする。
最も単純な方法として、各 y に対して上の数値積分をしてしまうと、分割点数 N に対して O(N²) の計算コストがかかってしまい、N が大きくなると計算のネックとなりかねない。 そこで高速フーリエ変換を利用して上の畳み込みを実行することで、計算コストのオーダーを軽減したい。FFTの計算コストはO(N log N)、また変換後の畳み込みは（単に N 回のかけ算になり）O(N)、全体で O(N log N) に軽減される。
高速フーリエ変換ライブラリFFTW3を利用することにする。