Mathematica による固有値計算の高速化 Eigenvalue calculation speed by Mathematica 情報工学部 06A2055 平塚翔太.

Presentation on theme: "Mathematica による固有値計算の高速化 Eigenvalue calculation speed by Mathematica 情報工学部 06A2055 平塚翔太."— Presentation transcript:

1 Mathematica による固有値計算の高速化 Eigenvalue calculation speed by Mathematica 情報工学部 06A2055 平塚翔太

2 スライド一覧 前回のあらすじ 自己相関 行列の対角化 行列のスペクトル分解 プログラムの内容 参考文献 バックグラウンド

3 前回のあらすじ VPN 下でのストリーミング配信における人の振舞い（デー タ等の劣化によりクライアントがキャンセルかリトライす る確率）を行列化する。 α β p p : キャンセルした確率 rp r : リトライした確率 (1 - r)p 1-α α 0 ・・・・・・・ 0 行列化 β 1-α-β α ・・・・・・・・ 0 ・ β 1-α-β α ・・・・・・ 0 ・・・・・・・・・・・・・・ 0 0 0 0 ・・・・・・・ 1-β β Client

4 自己相関 同じ時系列での相関 ｘ k+t 0 秒後 ⇒ 0 本 1 秒後 ⇒ 5 本 2 秒後 ⇒ 3 本 ： ｘ k ｘ k 秒後 r を相関係数という ： r = 1 ： 正の相関 ｘ k+t 秒後 r = -1 ： 負の相関 ｘ k とｘ k+t の相関グラフ r = 0 ： 相関無し r = 0 r = 1 r = -1 0123456789

5 t 秒時の相関係数 r (r (t) ) は r (t) = と定義される 分散（ Variance ） 複数のデータの二乗和を求めることで データの散らばり具合が求まる Var( ｘ k ) = ∑ ( ｘ k ) P ( ｘ k ) – ｘ P( ｘ k ) はある状態からｘ k になる確立を表す Var( ｘ k+t )Var( ｘ k ) Cov( ｘ k, ｘ k+t ) 22 ∞ ｘ k =0

6 P とｘ k の関係をグラフ化 ≈ ｘ k = ∑ ｘ k P ( ｘ k ) 定常 P ( ｘ k 、ｘ k+t ) ＝ P ( ｘ k+l 、ｘ k+t+l ) でどんな l でも成り立つとき P ( ｘ k 、ｘ k+t ) は定常である ｘkｘk P ・・・・ ｘ k+t 1 0 1 2 3 4 5 6 ・・・・ ｘkｘk ∞ ｘ k =0

7 共分散（ Covariance ） 複数のデータの積和を求めることで データ間の関係性や連動性が求まる Cov( ｘ k, ｘ k+t ) = ∑ ∑ ( ｘ k - ｘ k ) ( ｘ k+ ｔ - ｘ k+ ｔ ) P ( ｘ k, ｘ k+t ) ( ｘ k - ｘ k ) ：ｘ k からｘ k になる確率の変量 ( ｘ k+ ｔ - ｘ k+ ｔ ) ：ｘ k+ ｔ からｘ k+ ｔ になる確率の変量 P( ｘ k, ｘ k+t ) ：ｘ k からにｘ k+ ｔ なる確率 ∞ ｘ k =0 ∞ ｘ k+t =0

8 また、相関係数 r (t) とデータを転送する時間 t のグラフを 以下に示す 長いデータを転送 ⇒ 時間がかかる分、相関が比較的長い 間相関が強くなる 短いデータを転送 ⇒ 時間がかからない分、相関が比較的 すぐ相関が弱まる r(t) t 0 データ：長 データ：短

9 行列の対角化 固有値 ある行列 A に対して「 A ｘ = λ ｘ」を満たす ベクトルｘと、スカラー λ が存在するとき、 λ ：固有値 ｘ：固有ベクトル と呼ぶ。 「方向を持たない大きさ」 行列 A には固有ベクトルという方向と 固有値という大きさからなる

10 なぜ固有値なのか？？？ ここで、固有ベクトルｘを列ベクトル S とする そして、対角成分に固有値を並べた対角行列を Λ とする これらの行列から A S = Λ S がわかる これを変形すると S A S = Λ となる この S を A の対角行列という S = ｘ 1 ，ｘ 2 ，・・・，ｘ n λ1 λ2 Λ = ・ ・ λ ｎ ０ ０

11 S A S = Λ は、 S Λ S = A とも書ける ここで、行列 A を n 乗算したとき A と書く 固有値と固有ベクトルを用いると行列の乗算が著しく簡略化される n A = A A A A ･･･ A = SΛS SΛS SΛS SΛS ･･･ SΛS = SΛΛΛΛ ･･･ ΛS = SΛ S n n λ1 λ2 Λ = ・ ・ λ ｎ ０ ０ n n n n ※ S S = I

12 行列のスペクトル分解 行列 A 、固有値 λ 、とするとき直交する固有ベクトルを選ぶと = と表すことができる。これを と転置する。 A ｙ 1 ，ｙ 2 ，・・・，ｙ n λ1 λ2 ・ λ ｎ 0 0 ｘ 1 ，ｘ 2 ，・・・，ｘ n A = ｘ 1 ，ｘ 2 ，・・・，ｘ n λ1 λ2 ・ λ ｎ 0 0 ｙ1ｙ2・・・ｙnｙ1ｙ2・・・ｙn

13 A = λ 1 ｘ 1 ｙ 1 + λ 2 ｘ 2 ｙ 2 + ・・・ + λ n ｘ n ｙ n これを行列 A のスペクトル分解という ｘ i ｙ i ：行列 λ i ：スペクトル A = λ 1 ｘ 1 ｙ 1 + λ 2 ｘ 2 ｙ 2 + ・・・ + λ n ｘ n ｙ n A が n 乗の時の固有値 λ の m 乗を求めることができる mmm n ｙ ｘ 0 ｘiｘi ｙiｙi λ ｘiλ ｘi λ ｙiλ ｙi

14 プログラムの内容 VPN 誰が（何人）キャンセル するかわからない

15 キャンセル率の最も多い時を h MAX として定量化する 例： h MAX ：キャンセル率が最大 Δ ： 0 から h MAX を刻む数 σ ： h MAX * Δ ：定量化した時の一めもり w ：配信が正常に行える最大数 el ：終了 0 1 2 w+1 w+2 ・・・・・・・ el 配信の劣化が始まる h MAX σ

16 ストリーミングを受けるクライアントが増加するとキャンセル 率は増加、あるいは不変な場合はあるが、減少することはない と仮定する 0 1 2 w+1 w+2 w+3 ・・・・・ el 下がることはない 上がるか変わらないのは 有り ストリーミング配信の悪化増 h MAX σ

17 青線のみを Δ + １進数で定量化する その内の最大値 (relaxmax) と最小値 (relaxmin) を出力する 0 1 2 w+1 w+2 ・・・・・ el h MAX σ

18 プログラム

19 参考文献 相関係数と回帰直線 加藤千恵子、石村貞夫 著 秋田工業専門学校ＨＰ http://akita-nct.jp/ http://akita-nct.jp/ Wikipedia http://ja.wikipedia.org/wiki/ http://ja.wikipedia.org/wiki/ やさしく学べる線形代数 石村園子 著 千葉大学理学部ＨＰ http://www.math.s.chiba-u.ac.jp/ http://www.math.s.chiba-u.ac.jp/

20 御清聴ありがとうございました