高速フーリエ変換
(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
2つの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 )
上のように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)
前の例を異なる方法で整列する
① 2つの整列したファイルをを2次元ではな
く1次元の数列として書く.
最初に1列目の内容,次に2列目の内容
と表わす.
② 1次元の数列を半分に分けて,前半と後
半を交互に並び替える.
③ 比較・交換すべきところを比較・交換する.
④ 整列するまで②,③の操作を繰り返す.
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個の要素の2つのファ
イルが約lgN回のステップで併合できる.
• ステップ毎の操作から導かれる接続パター
ンはまったく同じ.
• 奇偶併合法は前の例よりも簡単に機械上
の配線で表わすことができる.
12
双単調併合法(bitonic merge)
• 奇偶併合法と同様に,表の各行に対する
分割と挿入の操作で併合する.
• 奇偶併合法とは異なる点
 第一ステップにおいて2番目に並ぶファイルを
逆順に整列すること
 奇偶併合法では最初の段の比較・交換素子
の位置が,それ以降の段と1つずつずれてい
るが,この方法ではそろっている.
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個の相異なる点x1, x 2 ,...,x n
における値がf ( x )の値に一致するような
fの連続な近似式 f n ( x ) のことを
f ( x )の補間式,あるいは補間公式という.
f n (x j )  f (x j )
( j  1,2,...,n )
 (※)
ここで,点x
1, 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
ダウンロード

第二回分 - TNT