はじめに
この記事は、以下の記事の続きで書かれています。 以下の記事を読んでいただき、その後この記事を読まれるのが一番読みやすいと思います。
記法について
$N$を$2^p$とします。 多項式$F(x)$を数列$A_0,A_1,\ldots,A_{N-1}$を用いて、
\begin{align} F(x) := \sum_{j = 0}^{N-1} A_j x^j \end{align}
と定義します。 また、多項式$E,O$を$F$に依存する形で、
\begin{align} E(x) &:= \sum_{j = 0}^{N/2} A_{2j}x^j\\ O(x) &:= \sum_{j = 0}^{N/2} A_{2j+1}x^j \end{align}
と定義します。
StockhamのFFT
大前提としてFFTは、分割統治法を用いて問題を半分にしていき、一番小さいところまで来たらまとめあげるという形でした。 具体的には、多項式$F(x)$を小さい多項式$E(x),O(x)$に分割し、それぞれにFFTを計算します。 その後、まとめあげるという形を取ります。 まとめる際、用いる漸化式は以下の形をしています。
\begin{align} F(\omega^k) = \left\{\begin{matrix} E(\omega^{2k}) + \omega^kO(\omega^{2k}) & (k\leq N /2 - 1\text{のとき})\\ E(\omega^{2k - N}) - \omega^{k - N/2}O(\omega^{2k - N}) & (k\geq N /2\text{のとき})\\ \end{matrix}\right. \end{align}
Cooley-TurkeyのFFTは、このまとめる際に2つの値から2つの値を導出する点を用いて、in-placeにFFTを計算していくことを行いました。 しかし、うまいこと2つの値から2つの値に導出するために初めに係数$A_k~(0\leq k\leq N - 1)$を並べ変えてから計算を行います。 この点をどうにかしたいというモチベーションがあります。つまり、$A_0,A_1,\ldots,A_{N-1}$という順番で入った状態を入力とし、$F(\omega^{0}),F(\omega^{1}),\ldots,F(\omega^{N-1})$という順番で出力を求めたいです。
さて、これを実現するためにどうすればいいでしょうか。 まず、in-placeで計算を行う点をあきらめます。具体的には係数が入っていた配列のほかに長さ$N$の配列を用意します。これら2つの配列を交互に使いまわすことで漸化式を計算していくことを考えます。 これは、競プロでDPの問題でよく見るメモリ節約術ですね。
はい、以上でStockhamのFFTの説明が終わりました……ということにしてもいいのですが、具体例を見て終わりたいと思います。 ここでは、実際に$N=8$での例を見たいと思います。
係数の分割は次のように行われます。
\begin{align} \text{0段目}&&&&\{0,1,2,3,&4,5,6,7\}&&\\ \text{1段目}&&&&\{0, 2, 4, 6\}, & \{1,3,5,7\}&&&\\ \text{2段目}&&\{0, 4\}, && \{1, 5\}, & \{2, 6\}, &&&\{3, 7\} \end{align}
さて、ここから入力を入れ替えずにどうやって係数をまとめるか？ということが問題になります。
上の分割を見ると2段目では、$A_j, A_{j+4}~(0\leq j\leq 3)$というペアでまとめ、それぞれ$2$のFFTの結果を求めることになります。 同様に1段目では、$A_j, A_{j + 2}, A_{j+4}, A_{j + 6}~(0\leq j\leq 1)$という組み合わせになり、それぞれ$4$個のFFTの結果を持つことになります。
後は、これを管理しやすい方法で1次元の配列に並べればよいです。 具体的には、2段目では$4\times 2$という形で、1段目では$2\times 4$という形で、1次元の配列にパックしてあげればよいです。
おわりに
ちょっと雑になりましたが、名前がついている割に中身はすごいことはやっていないと思います。 ただ、このような計算テクニックで並列化しやすい等のメリットが大きいのだろうと思いました。
