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

高速フーリエ変換
(fast Fourier transform)
11月24日
第2回目発表
1
今回のテーマ
• 完全シャッフル
– 並列アルゴリズム・・・計算機に一度に1つず
つ命令を実行させるのではなく，多数の処理
を同時に行わせる．プログラムを1台ではなく
M台のプロセッサによって処理をする．
• ラグランジュの補間公式
2
前回の復習
2つのN - 1次多項式の積の計算を考えた．
◎2つのN  1次多項式の積を求める時，
普通に掛けると，乗算の回数は N 2回
高速フーリエ変換を使うと，
2 N lg N  ON 回
◎高速フーリエ変換を用いた積の計算手順
①：
2つのN  1次多項式を 2 N  1個の異なる点で計算する．
（このとき
1のN乗根を使う）
 分割統治法を用いて，高速フーリエ変換で計算する．
②：変換した値を掛け
合わせる．
③：①と同じ計算手順により補間する．
 逆フーリエ変換を用いる
3
２つのN-1次多項式
P(x)
Q(x)
評
価
乗算
N2の計算時間
フーリエ変換
分割統治法を用いて
効率よくしたのが高速フーリエ変換
p(a1 ),, pa 2 N1 
q(a1 ),, qa 2 N1 
乗算
2N-1次の多項式
R(x)=P(x)Q(x)
補
間
逆フーリエ変換
r ( x )  p ( x )q ( x )
r (a1 ),, r (a 2 N1 )
4
完全シャッフル(perfect shuffle)
• 分割統治法を用いて評価をする際に完全シャッ
フルを使う．
例）
p( x )  p 0  p1x  p 2 x 2  p 3 x 3  p 4 x 4  p5 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 (p1  p 3 x 2  p5 x 4  p 7 x 6 )
 p e ( x 2 )  xpo ( x 2 )
上のように２つに分割する．
前回は，
完全シャッフルをすることにより
配列の前半に連続して偶数番目の係数を入れ，
後半に奇数番目の係数を入れることが出来る．
と説明した．今回はもう少し詳しく説明をしていく． 5
2つの整列をしたファイルの併合
•
•
“比較・交換”命令により併合するアルゴ
リズムを考える．
手順
① 一方のファイルを他方のファイルの下に書く．
② 縦に並んだもの同士を比べて，大きい方が
下になるように交換する．
③ 各行を半分に分けて，後半をもとの行の下
に挿入
④ 第2行目の項目と3行目の項目とを比較して
大きいほうが下になるように交換
(注意)他の行との比較は元々整列している
おかげで必要ない
6
A E G G I M N R
A
A
A B E E L M P X
B
A
A
B
E
E
E
E
E
E
G
G
G
G
I
I
M
L
L
M
M
M
A B E E
N
N
A E G G
R
P
I
M N R
P
R
L M P X
X
X
A B E E I M N R
A E G G L M P X
A B E
I
M N R
A E
L
E
G G
M P
X
A B
A B
E E
A E
A E
E E
G G
G G
I
I
M
M
N R
L M
L M
N R
P X
P X
7
• 一般の場合の操作は
 各行を半分に分けて，後半を元の行の
下に挿入し，異なる行から来た上下に隣
り合う項目の比較・交換を行う．
 1回操作を行う度に行の数は倍、列の数
は半分になり，行も列も整列している．
例題では，
8行2列→4行4列→2行8列→1行16列
となり整列した列が得られる．
8
性質
N個の要素を含む整列したファイル2つを併合するのに，
約 lg N回の並列計算ステップが必要．
前の例では，lg 8  3回の並列計算ステップ．
もしN  2 n であれば，
例題のようにnステップかかる．
( N  2 n だからn  lg N)
大きさが2のベキ乗ではないデータに対しては，
単純にダミーのキーを加えればよい．
9
奇偶併合法
(odd-even merge)
前の例を異なる方法で整列する
① ２つの整列したファイルをを２次元ではな
く１次元の数列として書く．
最初に１列目の内容，次に２列目の内容
と表わす．
② １次元の数列を半分に分けて，前半と後
半を交互に並び替える．
③ 比較・交換すべきところを比較・交換する．
④ 整列するまで②，③の操作を繰り返す．
10
A E G G I
M N R A B E E L M P
X
A A E B G E G E I
L M M N P
R X
A A B E E G E G I
L M M N P
R X
A I
A L B M E M E N G P
A A I
L B E M M E G N P
E R G X
E G R X
A E A G I
N L P
B E E G M R M X
A A E G I
L N P
B E E G M M R X
A B A E E E G G I
M L M N R P
A A B E E E G G I
L M M N P
X
R X
11
• 前の例と同様に，N個の要素の２つのファ
イルが約lgN回のステップで併合できる．
• ステップ毎の操作から導かれる接続パター
ンはまったく同じ．
• 奇偶併合法は前の例よりも簡単に機械上
の配線で表わすことができる．
12
双単調併合法(bitonic merge)
• 奇偶併合法と同様に，表の各行に対する
分割と挿入の操作で併合する．
• 奇偶併合法とは異なる点
 第一ステップにおいて２番目に並ぶファイルを
逆順に整列すること
 奇偶併合法では最初の段の比較・交換素子
の位置が，それ以降の段と１つずつずれてい
るが，この方法ではそろっている．
13
A E G G I
M N R X P
A X E P
G M G L I
A X E P
G M G L E I
A E X I
E E P
A E I
M L E E B A
E M E N B R A
E M B N A R
M G B M N G A L R
X E E M P
B G M N A G L R
A B E G I
M X N E A E G M L P
R
A B E G I
M N X A E E G L M P
R
A A B E E E G G I
L M M N P
X R
A A B E E E G G I
L M M N P
R X
14
A E G G I
M N R
X P M L E E
B A
A E G G E E
B A
A
A
A
A
B
B
E
E
A E
A A
E
E
B A
B E
E
E
E E
E E
G
G
G G
G G
G
G
I
I
I
I
L
L
M
M
M
M
N
N
E E G G
P
P
I
X
R
R
X
X P M L I
M N R
A E
G G
E
E
B A
X P
M L
I
M N R
A E B A
M M L
X P
N R
M
L
M L
M M
X P
N P
N R
X R
15
• 比較・交換素子間の接続パターンだけでな
く，その位置まで規則性がある．
• 素子の数は奇偶併合法より多いが，ステッ
プの数が同じだから，このことは問題とな
らない．
• 隣り合った項目全てを比較・交換するため，
奇偶併合法より単純な機械で実現できる．
16
ラグランジュ補間公式
• 前回の例）
p( x )  1  x  x 2
q( x )  2  x  x 2
r x   p( x )q( x )を求めたい
x  2,1,0,1,2においてpx , qx を計算すると
p(2), p(1), p(0), p(1),p(2)  3,1,1,3,7
q(2), q(1), q(0), q(1),q(2)  8,4,2,2,4
となる．すると
r ( x )は
r(2), r(1), r(0), r(1),r(2)  24,4,2,6,28
17
ラグランジュの公式を用いると
x 1 x  0 x 1 x  2
r ( x )  24
 2 1  2  0  2 1  2  2
x  2 x  0 x 1 x  2
4
1 2 1  0 11 1  2
x  2 x 1 x 1 x  2
2
0  2 0 1 0 1 0  2
x  2 x 1 x 1 x  2
6
1 2 11 1 0 1 2
x  2 x 1 x  0 x 1
 28
2  2 2 1 2  0 2 1
   2  x  2x 2  x 4
となる．
18
前回の説明
N  1次多項式 P (x)のN個の点 x1 , x 2 ,, x Nと
そこでの値y1 , y 2 ,, y Nが与えられた時、
P( x1 )  y1 , P( x 2 )  y 2 , , P( x N )  y N
を満たす唯一の N  1次多項式を求めたい．（補間する）
この時の古典的な解はラグランジュの補間公式を用いること
x  xi
P( x )   y j 
1 j N 1i  N x j  x i
（ラグランジュの補間
公式）
i j
• 今回はもう少し詳しく説明したいと思う．
19
n個の相異なる点ｘ１, x 2 ,...,x n
における値がf ( x )の値に一致するような
fの連続な近似式 f n ( x ) のことを
f ( x )の補間式，あるいは補間公式という．
f n (x j )  f (x j )
( j  1,2,...,n )
 (※)
ここで，点ｘ
１, x 2 ,...,x n を標本点という．
f (n )はn  1次式であるとする．
またここでは，補間公
式 f n ( x ) が多項式であるとする．
20
そこで，
f n (x) 
 f (x )L
1 j n
j
( n 1)
j
( x ) （※※）
とおいてみる．
Lj
( n 1)
( x )はxに関して高々N  1次多項式である．
(※)を満たすためには L j
( n 1)
( x ) は以下の条件を
満たさなければならない．
Lj
( n 1)
0 ; x  x k , k  j
(x)  
1 ; x  x j
21
この条件を満たす多項式は一意的に次式となる．
Lj
( n 1)
(x) 
( x  x1 )(x  x 2 )  ( x  x j1 )(x  x j1 )  ( x  x n )
( x j  x1 )(x j  x 2 )  ( x j  x j1 )(x j  x j1 )  ( x j  x n )
x  xi

1i  n x j  x i
i j
これを（※※）に代入
すると，ラグランジュ
補間公式
x  xi
f n (x)   f (x j ) 
1 j n
1i  n x j  x i
i j
が得られる．
22

Download Report