Mathematicaによる固有値 計算の高速化 Eigenvalue ca

MATHEMATICAによる固有値計算の高速化
EIGENVALUE CALCULATION
SPEED BY
MATHEMATICA
情報工学部 情報工学科
06A2055
平塚 翔太
スライド一覧
•はじめに
•研究概要
•Mathematicaについて
•改良点
•研究結果
•まとめ
•参考文献
はじめに

先生に勧められ、かつ1年間熱心に研究できるテーマ
だと思い、本研究を行った。
研究概要

VPNの下でのストリーミング配信の劣化
劣化
VPN

仮定
キス
ャト
ンリ
セー
ルミ
すン
るグ
確配
率信
を
Max
0
1
2
3
el
el+1 el+2 el+3
ストリーミングの本数増加
ストリーミング配信サービスの劣化
n

プログラム内容
α
1
α
2
β
α
3
β
α
4
β
α
5
β
0
ストリーミングの本数
6
β
α:増加する確率
β:減少する確率
第二固有値
固有値計算
0
確率行列
(三重対角行列)
緩和時間
MATHEMATICAについて
{}で囲まれた複数の要素⇒リスト
 ベクトル,行列,集合,数列,データを扱うにあたっての
標準的な形式
 リストを使い高速化を目指す

リスト
改良点1

行列作成プログラムがボトルネック

DiagonalMatrix関数とSparseArray関数
三重対角行列を作成するのに用いる
DiagonalMatrix SparseArray
処理速度(s)
0.515
0(測定範囲超過)
メモリ数(byte)
800,000,088
160,528
図:10000×10000の行列を作成

DiagonalMatrix

SparseArray
改良点2

複雑な計算をする組み込み関数の中に組み込み関数を多用すると処理
時間がかかる.
A: SparseArray[Array[~], Rest[~],~]
B: a=Array[~]
b=Rest[~]
SparseArray[a, b,~]
処理速度(s)
プログラムA
プログラムB
14.321
0.843
改良点3

リスト処理関数で二重リストを処理させるより,手続き関数を用いてリスト処
理させる方がメモリを多用せずにすむ.
{ { a,a,a,a,a },{ b,b,b },・・・,{ z,z,z,z } }
計算処理
メモリ大
{ { 行列A },{ 行列B },・・・,{ 行列Z } }
For[~, ~, ~,
{ a,a,a }
計算処理
メモリ小
{ 行列A }
固有値計算へ
]
研究結果

最大ストリームについて
作成
オリジナル
1400
1200
1000
処
理
速
度
(
s
)
800
600
400
200
0
10
100
1000
n
10000
100000

el(キャンセル率の最大)について
作成
オリジナル
4500
4000
3500
3000
処 2500
(理
s
速
2000
)
度
1500
1000
500
0
12
13
14
15
el
※el=18からメモリ不足により測定不可能
16
17
まとめ
処理速度とメモリ量はトレードオフの関係である
 同じ計算をする関数でも構造が異なるのでよく検証すること
 組み込み関数のみでコーディングするより手続き関数を用
いた方が高速化できる場合がある.

参考文献

Mathematica Document Center
http://reference.wolfram.com/mathematica/guide/Mathematica.ja.html

入門Mathematica
日本Mathematicaユーザ会:編著

K.Oida ,On the inpact of Qos-sensitivity on
correlation structures,ELSEVIER,Computer
Networks 52 (2008) 351-359
御清聴ありがとうございました