1 高速フーリエ変換 (fast Fourier transform)

2 高速フーリエ変換とは？ – 簡単に言うとフーリエ変換を効率よく計算 する方法 – アルゴリズムの設計技法は分割統治法に基 づいている 今回の目的は？ – 多項式の積を求める問題を取り上げ、高速 フーリエ変換のアルゴリズムを用いた解法 を導いて、計算時間を驚くほど短縮できる ことを示す

3 多項式の積の計算の例１ 以下のような 2 次多項式のｐ（ｘ）とｑ（ｘ）をかけ る この場合２次式のため簡単に出来たが、一般 的に N-1 次多項式の時は、このような方法で は大変時間 がかかる. どうすれば よいのか？

4 多項式の積の計算を高速化するに は？ N-1 次の多項式は N 個の異なる点におけ る関数値で完全に決まるという事実を 利用する（ N-1 次式の項の数は定数も含 むから N 個） ⇒２つの N-1 次多項式同士の積は２ N-1 個の点 でその多項式の値が分かっていれば、その 積を完全に決定できる

5 ２つの N-1 次多項式の積を求める 基本 的な手順 評価：入力された多項式の値を２ N-1 個 の 異なる点で計算する 乗算：各点でえられた値を掛ける 補間：上で求めた２ N-1 個の値を補間す る – 補間とは、多項式の N 個の異なる点におけ る値が与えられた時、その多項式の係数を 求めること

6 2N-1 次の多項式 R(x)=P(x)Q(x) ２つの N-1 次多項式 P(x) Q(x) 乗算 フーリエ変換 逆フーリエ変換 分割統治法を用いて 効率よくしたのが高速フーリエ変 換

7 例２）

8

9 ラグランジュの公式

10 例２の場合、評価と補間それぞれで の計算時間がかかってしまう しかし、多項式の値を計算する２ N-1 個 の点はどこの点を選んでもよいことに 注目すると、多項式の積の計算を簡単 にする点集合を選べば、効率のよく計 算時間を短縮できるのでは？

11 １の複素累乗根 多項式の積の計算をする点として、１ の複素累乗根を用いると計算を高速化 できる

12

13 N-1 次多項式の値を １の N 乗根において計 算する 1 の N 乗根における値をそのまま計算し たのではあまり意味がない 分割統治法を用いる – 低次の項から順に交互にとって２つに分け る –N- １次多項式の値を N 個の点で計算するた めに、まず N/2 個の係数の２つの多項式に 分割する。そしてそれぞれの多項式の値を N/2 個の点で計算して全体の N 点における値 を求めればよい

14 なぜ分割統治法がいいのか？ – 根を２乗すると別の根が得られる – 特に N が偶数の時は、 １の N 乗根を２乗すると、１の N/2 乗根が 得られる 例） 実際に N=8 で考えてみる

15

16

17

18

19

20 １の累乗根の関数値の補間 １の累乗根を用いて高速で多項式の値が得られ た ⇒その値を高速で補間すれば、高速で多項式の積 が求まったことになる． 補間する点集合が１の累乗根ならば、 関数値を計算する手順で補間多項式も求まる！ フーリエ変換とその逆変換を使っているから！！ なぜな ら

21

22

23

24 性質４１．２ １の N 乗根における値が与えられた N-1 次多項式の係 数を、約 NlgN 回の乗算で求めることが出来る． これは補間の計算は多項式の値の計算の逆であるか ら性質４１．１より乗算は約 NlgN 回となる． 多項式の値の計算と補間の計算の乗算の回数は NlgN 回であるが、あくまで１の N 乗根に対してだけ あてはまる

25 eval(p, outN, 0); eval(q, outN, 0); for (i = 0; i <= outN; i++) r[i] = p[i]*q[i]; eval(r, outN, 0); for (i = 1; i <= N; i++) { t = r[i]; r[i] = r[outN+1-i]; r[outN+1-i] = t; } for (i = 0; i <= outN; i++) r[i] = r[i]/(outN+1); ・大域変数 outN に２ N-1 が与えられている． ・ p,q,r は添字の範囲が０から２ N-1 の複素数の配列 と仮定されている． ・多項式 p,q は N-1 次であり、 N 次より上位の係数は０ に 初期化されている．

26 手続き eval １番目の引き数 – 多項式の係数を、１の累乗根における多項 式の値に書き換える ２番目の引き数 – 多項式の次数（係数の数、１の根の数より １少ない） 手続き eval の目的 N+1 個の係数が連続して入っている配列を入力 と して、同じ配列に N+1 個の関数値を入れて返す こと

27 しかし、再帰呼出しでは連続していない偶数 番目と奇数番目の係数の配列を入れかえなけ ればならない． ⇒ここで用いられるのが、完全シャッフル 完全シャッフルをすることにより 配列の前半に連続して偶数番目の係数を入れ、 後半に奇数番目の係数を入れることが出来る．

28 完全シャッフル P[0] P[1] P[2] P[3] P[4] P[5] P[6] P[7] P[0] P[2] P[4] P[6] P[1] P[3] P[5] P[7]

29 高速フーリエ変換のプログラ ム 実際計算する時の 1 の N 乗根の値は、 配列 w に 1 の (outN+1) 乗根が入っている 上のことも考慮すると 次のような高速フーリエ変換のプログ ラムとなる．

30 eval(struct complex p[], int N, int k) { int i, j; if (N == 1) { p0 = p[k]; p1 = p[k+1]; p[k] = p0+p1; p[k+1] = p0-p1; } else { for (i = 0; i <= N/2; i++) { j = k+2*i; t[i] = p[j]; t[i+1+N/2] = p[j+1]; } for (i = 0; i <= N; i++) p[k+i] = t[i]; eval(p, N/2, k); eval(q, N/2, (k+1+N)/2); j = (outN+1)/(N+1); for (i = 0; i <= N/2; i++) { p0 = w[i*j]*p[k+(N/2)+1+i]; t[i] = p[k+i]+p0; t[i+(N/2)+1] = p[k+i]-p0; } for (i = 0; i <= N; i++) p[k+i] = t[i]; }

31 性質４１．３ 2 つの N-1 次多項式の積は 2NlgN+O(N) 回 の複素数の計算によって求められる． 性質４１．１と性質４１．２より、 N-1 次多項式を 1 の N 乗根の値への変換と補 間の乗算の回数はそれぞれ NlgN 回であ る．また 1 の N 乗根に変換した値を掛け 合わせるのに O(N) の乗算が必要だから、 積の回数は 2NlgN+O(N) 回となる．

32