高速フーリエ変換
(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  x  x )
2
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の複素累乗根
一般にその数を累乗して1となる複素数は
数多くあり,その複素
数を1の複素累乗根という.
実際,自然数Nに対して,
Z  1となる複素数ZがN個ある.
N
これらの中の1つは「
1の原始N乗根」とよばれ,
それをWN と表わすと,全ての根は
k  0,1,2,, N  1に対して,WN をk乗してえられる.
8


2


1
ここでWN  exp
とする.

N

例)1の8乗根
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が原始8乗根である .
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 )  p 0  p1x  p 2 x 2  p 3 x 3  p 4 x 4  p 5 x 5  p 6 x 6  p 7 x 7
 (p 0  p 2 x 2  p 4 x 4  p 6 x 6 )  x (p1x  p 3 x 2  p 5 x 4  p 7 x 6 )
 p e ( x 2 )  xpo ( x 2 )
上のように2つに分割する.
(p 0 ,  , p 7 は多項式 p( x )の係数 )
ここで,
7次多項式 p( x ) を1の 8乗根で計算する.
W8 : w 80 , w 18 , w 82 , w 83 , w 84 , w 85 , w 86 , w 87
まず,w 84  1だから
W8 : w 80 , w 18 , w 82 , w 83 , w 80 , w 18 , w 82 , w 83
となる.次に各項を2
乗すると
W82 : w 04 , w 14 , w 24 , w 34 , w 04 , w 14 , w 24 , w 34
になる.
11
p( x )  p e ( x )  xpo ( x )
2
2
に注目すると以下のような次式が導かれる.
p( w 80 )  p e ( w 04 )  w 80 p o ( w 04 ),
p( w 18 )  p e ( w 14 )  w 18 p o ( w 14 ),
p( w 82 )  p e ( w 24 )  w 82 p o ( w 24 ),
p( w 83 )  p e ( w 34 )  w 83 p o ( w 34 ),
p( w 84 )  p e ( w 04 )  w 80 p o ( w 04 ),
p( w 85 )  p e ( w 14 )  w 18 p o ( w 14 ),
p( w 86 )  p e ( w 24 )  w 82 p o ( w 24 ),
p( w 87 )  p e ( w 34 )  w 83 p o ( w 34 ),
12
実際に p( w 85 )  p e ( w14 )  w18 p o ( w14 ) を計算してみる.
p( w 85 )  p e ( w14 )  w18 p o ( w14 )
 (p 0  p 2 w14  p 4 w 24  p 6 w 34 )  w18 (p1  p 3 w14  p 5 w 24  p 7 w 34 )
 (p 0  p 4 w 24 )  w14 (p 2  p 6 w 24 )  w18{( p1  p 5 w 24 )  w 14 (p 3  p 7 w 24 )}
 (p 0  p 4 w12 )  w14 (p 2  p 6 w12 )  w18{( p1  p 5 w12 )  w 14 (p 3  p 7 w12 )}
ここで、
w12  1だから
 (p 0  p 4 )  w14 (p 2  p 6 )  w18{( p1  p 5 )  w14 (p 3  p 7 )}
またw  ( w )
1
w  (w )
1
1
4
1
8
1
2
1
4
2
2
 (1)
 (i)
1
2
1
2
 i,
 i だから
 (p 0  p 4 )  i(p 2  p 6 )  i{( p1  p 5 )  i(p 3  p 7 )}
13
一般的に 1のN乗根における p( x ) の計算方法
p e x とp o x を1の N / 2 乗根において再帰的に 計算する.
(ただし,再帰的な計
算で N / 2, N / 4,となるので
N は 2 のベキ乗であると仮定する.)
再帰は w 2x のようにN  2 の時に打ち切る.
このときw  1, ( w )  1 のどちらかだから
1
2
1 2
2
p 0  p1x は p 0  p1 か p 0  p1 を得る.
あとは1つずつ上に統合して,全体の p( x ) を求める.
分割統治法を用いたこの再帰的な
計算が高速フーリエ変換である.
14
まとめ
• 高速フーリエ変換を用いることで,多項式の乗算
回数をN2回から2NlgN+O(N)回に減らすことがで
きる.低い次数ではたいした差が出ないが,次数
が大きくなればなる程計算時間に大きな差が出
る.
• 今後の課題
評価の再帰的計算でNは2のベキ乗であると仮
定したが,2のベキ乗ではないときはどうするか
を勉強していきたい.
15
• 今回は評価についてだけ述べた.多項式の積の計算
はまだ乗算と補間を行わないといけないが,今回は
時間が少ないため省略した.高速フーリエ変換につ
いての今までの発表分は
http://tnt.math.metro-u.ac.jp/labo/grad/2004/akira/index.html
に載せてある.
16
ダウンロード

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