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

高速フーリエ変換
(fast Fourier transform)
東京都立大学
理学部数学科4年
宮崎彬
1
発表の流れ
高速フーリエ変換について全てを説明する
と時間が足りなくなってしまう．
高速フーリエ変換を説明する為の概要を簡
単に述べる．
分割統治法を用いた高速フーリエ変換の
計算を詳しく説明していく．
2
高速フーリエ変換の概要
前提
• 高速フーリエ変換を述べる為に
2つのN-1次多項式の積の計算
を考える．
• 「N-1次多項式はN個の異なる点における
関数値で完全に決まる」という事実を利用
して，多項式の積の計算を高速化する．
3
高速フーリエ変換を用いた
高速化した乗算の手順
• 評価：2つのN-1次多項式を2N-1個の異な
る点で計算する．
• 乗算：変換した値を掛け合わせる．
• 補間：評価の逆変換をする，つまり評価と
同じ計算手順で求めたい2N-2次多
項式を求めることができる．
（補間とは，2N-2次多項式の2N-1個の異な
る点における値が与えられた時，その2N-2
次多項式の係数を求めること）
4
乗算の回数の違い
2つのN-1次多項式の乗算
• 普通に掛け合わせると，N2回の掛け算．
例）(1  x  x 2 )(2  x  x 2 )
 2  x  x  2x  x  x  2x  x  x
2
2
3
2
3
4
 2  x  2x 2  x 4
• 高速フーリエ変換を用いると
2NlgN+O(N)回の掛け算．
5
2つのN-1次多項式
P(x)
Q(x)
評
価
乗算
N2回の掛け算
フーリエ変換
分割統治法を用いて
効率よくしたのが
2N-2次の多項式
R(x)=P(x)Q(x)
補
逆フーリエ変換間
高速フーリエ変換
p(a1 ),, pa 2 N1 
q(a1 ),, qa 2 N1 
乗算
評価→乗算→補間
2NlgN+O(N)回の掛け算
r(x)  p(x)q(x)
r(a1 ),, r(a 2 N1 )
6
評価の計算
• 今回の発表では評価・乗算・補間の流れの
中で評価について述べたいと思う．
• 評価の方法



ただN-1次多項式に値αを代入して計算しても
意味がない．(αN-1の計算が必要になるから)
評価する2N-1個の点は異なる1の複素累乗根
を用いる．
評価の計算は分割統治法を用いる．
7
1の複素累乗根
一般にその数を累乗し
て１となる複素数は
数多くあり，その複素
数を１の複素累乗根と
いう．
実際，自然数
Nに対して，
Z  1となる複素数
ZがN個ある．
これらの中の１つは「
１の原始
N乗根」とよばれ，
それをWN と表わすと，全ての根
は
k  0,1,2,, N 1に対して，
WNをk乗してえられる．
N
8


2


1
ここでWN  exp
とする．

N

例）１の８乗根
0
8
1
8
2
8
3
8
4
8
5
8
6
8
7
8
W ,W ,W ,W ,W ,W ,W ,W
W80  1で，
W81が原始８乗根である　.
Nが偶数の時はWN 2 は 1であるから，
N
W84  1となる．
また1のN 乗根を　2 乗すると，
1の N / 2 乗根
が得られる．
よって，
(W81 )2  W41 , (W41 )2  W21 .
9
分割統治法
•
N-1次多項式の1のN乗根における値を
分割統治法を用いて求める．
①
N個の係数があるから，まずN/2個の係数の
2つの多項式に分割する．その際に低次の
項から順に交互にとって2つに分ける．
② 次にN/2個の係数の多項式の値を求めてか
ら，N個の係数のN-1次多項式の値を求める．
(統合する)

N/2個の係数の多項式の値が求まらない時は，
さらに2つに分けてN/4個の係数の多項式にする．
10
例）N  8の時
p(x)  p0  p1x  p2 x 2  p3x 3  p4 x 4  p5 x 5  p6 x 6  p7 x 7
 (p0  p2 x 2  p4 x 4  p6 x 6 )  x(p1x  p3x 2  p5 x 4  p7 x 6 )
 pe (x 2 )  xp o (x 2 )
上のように
2つに分割する．
(p0 ,, p7 は多項式p(x)の係数)
ここで，
7次多項式p(x) を1の8乗根で計算する．
W8 : w80 , w18 , w82 , w83 , w84 , w85 , w86 , w87
まず，
w84  1だから
W8 : w80 , w18 , w82 , w83 ,w80 ,w18 ,w82 ,w83
となる．次に各項を２
乗すると
W82 : w 04 , w14 , w 24 , w 34 , w 04 , w14 , w 24 , w 34
になる．
11
p(x)  pe (x )  xp o (x )
に注目すると以下のよ
うな次式が導かれる．
2
2
p(w80 )  pe (w 04 )  w80po (w 04 ),
p(w18 )  pe (w14 )  w18po (w14 ),
p(w82 )  pe (w 24 )  w82po (w 24 ),
p(w83 )  pe (w34 )  w83po (w34 ),
p(w84 )  pe (w 04 )  w80po (w 04 ),
p(w85 )  pe (w14 )  w18po (w14 ),
p(w86 )  pe (w 24 )  w82po (w 24 ),
p(w87 )  pe (w34 )  w83po (w34 ),
12
実際に p(w85 )  pe (w14 )  w18po (w14 ) を計算してみる．
p(w85 )  pe (w14 )  w18po (w14 )
 (p0  p2 w14  p4 w 24  p6 w 34 )  w18 (p1  p3w14  p5 w 24  p7 w34 )
 (p0  p4 w 24 )  w14 (p2  p6 w 24 )  w18{(p1  p5 w 24 )  w14 (p3  p7 w 24 )}
 (p0  p4 w12 )  w14 (p2  p6 w12 )  w18{(p1  p5 w12 )  w14 (p3  p7 w12 )}
ここで、
w12  1だから
 (p0  p4 )  w14 (p2  p6 )  w18{(p1  p5 )  w14 (p3  p7 )}
1 12
2
1
またw  (w )  (1) 2  i,
1
4
1 12
4
1
w  (w )  (i) 2  i だから
1
8
 (p0  p4 )  i(p2  p6 )  i{(p1  p5 )  i(p3  p7 )}
13
一般的に１のN乗根における
p(x) の計算方法
pe x とpo x を1の N / 2 乗根において再帰的に
計算する．
（ただし，再帰的な計
算でN / 2, N / 4,となるので
Nは 2のベキ乗であると仮定
する．）
再帰はw 2x のように
N  2の時に打ち切る．
このとき
w  1, (w )  1 のどちらかだから
p0  p1x は p0  p1 か p0  p1 を得る．
あとは1つずつ上に統合して，
全体のp(x) を求める．
分割統治法を用いたこ
の再帰的な
計算が高速フーリエ変
換である．
1
2
1 2
2
14
まとめ
• 高速フーリエ変換を用いることで，多項式の乗算
回数をN2回から2NlgN+O(N)回に減らすことがで
きる．低い次数ではたいした差が出ないが，次数
が大きくなればなる程計算時間に大きな差が出
る．
• 今後の課題
評価の再帰的計算でNは2のベキ乗であると仮
定したが，2のベキ乗ではないときはどうするか
を勉強していきたい．
15
• 今回は評価についてだけ述べた．多項式の積の計算
はまだ乗算と補間を行わないといけないが，今回は
時間が少ないため省略した．高速フーリエ変換につ
いての今までの発表分は
http://tnt.math.metro-u.ac.jp/labo/grad/2004/akira/index.html
に載せてある．
16

Download Report