Mathematicaによる固有値計算の高速化 Eigenvalue calculation speed by Mathematica

Slides:



Advertisements
Similar presentations
シミュレーション演習 G. 総合演習 ( Mathematica 演 習) システム創成情報工学科 テキスト作成: 藤尾 光彦 講義担当: 尾下 真樹.
Advertisements

Mathematica による固有値計算の高速化 Eigenvalue calculation speed by Mathematica 情報工学部 06A2055 平塚翔太.
HBSP モデル上での 行列積を求めるアルゴリ ム 情報論理工学 吉岡健太.
ユーザーイメージ収集 インターフェイスの開発
データ解析
Webプロキシサーバにおける 動的資源管理方式の提案と実装
CPUとGPUの 性能比較 -行列計算およびN体問題を用いて-
計算理工学基礎 「ハイパフォーマンスコンピューティングの基礎」
キャッシュ付PRAM上の 並列クィックソートと 並列マージソート
NFCを利用した登山者間DTNの構築 Building DTN for Climbers by using NFC
Flashプレイヤーを使った動画配信 情報工学科 宮本 崇也.
情報工学科 06A2055 平塚 翔太 Hiratsuka Shota
三重対角化アルゴリズムの性能評価 早戸拓也・廣田悠輔.
研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻.
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
確率論・数値解析及び演習 ─ 数値解析 ─ 第三章 (補足資料) 名古屋大学工学部電気電子・情報工学科 電気電子工学コース.
プライバシ協調フィルタリングにおける 利用者評価行列の次元削減
インターネット構成法 最終課題 ~ネットワークデザイン~.
土木計画学 第5回(11月2日) 調査データの統計処理と分析3 担当:榊原 弘之.
統計的仮説検定の考え方 (1)母集団におけるパラメータに仮説を設定する → 帰無仮説 (2)仮説を前提とした時の、標本統計量の分布を考える
AllReduce アルゴリズムによる QR 分解の精度について
地理情報システム論 第3回 コンピュータシステムおける データ表現(1)
確率モデルによる 画像処理技術入門 --- ベイズ統計と確率的画像処理 ---
応用数理工学特論 線形計算と ハイパフォーマンスコンピューティング
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
Peer to Peer(P2P)の概要と 研究の進捗
シミュレーション演習 G. 総合演習 (Mathematica演習) システム創成情報工学科
サーバ負荷分散におけるOpenFlowを用いた省電力法
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
文献名 “Performance Tuning of a CFD Code on the Earth Simulator”
Mathematicaによる固有値計算の高速化 Eigenvalue calculation speed by Mathematica
東京海洋大産学官連携研究員/技術コンサルタント 高須 知二 Tomoji TAKASU
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(NlogN)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似法
Mathematicaによる固有値計算の高速化 ~ Eigenvalue calculation speed by Mathematica ~ 情報工学科 06A2055 平塚 翔太.
画像処理③ 05A1027  後藤航太.
訓練データとテストデータが 異なる分布に従う場合の学習
「R入門」  5.7 行列に対する諸機能  10月23日 (木) 発表者 大城亜里沙.
通信機構合わせた最適化をおこなう並列化ンパイラ
MEMSセンサを用いたINS/GPS複合航法システム
変換されても変換されない頑固ベクトル どうしたら頑固になれるか 頑固なベクトルは何に使える?
Data Clustering: A Review
個人の動画配信のためのWebサーバ構築 06A1058 古江 和栄.
GPUを用いた疎行列の格納形式による行列ベクトル積の評価
目的:高速QR分解ルーチンのGPUクラスタ実装
第3章 線形回帰モデル 修士1年 山田 孝太郎.
統計ソフトウエアRの基礎.
秘匿リストマッチングプロトコルとその応用
遺伝アルゴリズムによる NQueen解法 ~問題特性に着目した突然変異方法の改善~
プログラミング入門2 第13回、14回 総合演習 情報工学科 篠埜 功.
高次元データにおける2次形式の近似について
藤本翔太1, 狩野裕1, Muni.S.Srivastava2 1大阪大学基礎工学研究科
停止ストリームの検知 情報工学部 情報工学科 06a2072 山下 雄
停止ストリームの検知(2).
Max Cut and the Smallest Eigenvalue 論文紹介
原子核物理学 第7講 殻模型.
SNS内のワームの早期検知システムの考案
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(Nlog2N)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似
精密工学科プログラミング基礎 第7回資料 (11/27実施)
MPIを用いた並列処理計算 情報論理工学研究室 金久 英之
密行列固有値解法の最近の発展 (I) - Multiple Relatively Robust Representation アルゴリズム - 2004年11月26日 名古屋大学 計算理工学専攻 山本有作 日立製作所の山本有作です。 「~」について発表いたします。
シミュレーション演習 G. 総合演習 (Mathematica演習) システム創成情報工学科
Webページタイプによるクラスタ リングを用いた検索支援システム
キャッシュマシン向け三重対角化 アルゴリズムの性能予測方式
精密工学科プログラミング基礎Ⅱ 第2回資料 今回の授業で習得してほしいこと: 配列の使い方 (今回は1次元,次回は2次元をやります.)
目次 はじめに 収束性理論解析 数値実験 まとめ 特異値計算のための dqds 法 シフトによる収束の加速
分散メモリ型並列計算機上での行列演算の並列化
プログラミング基礎a 第5回 C言語によるプログラミング入門 配列と文字列
インセンティブにより自律ユーザに 高品質なオーバーレイマルチキャスト木を 構築させるプロトコルの提案
ランダムプロジェクションを用いた音響モデルの線形変換
転移学習 Transfer learning
Presentation transcript:

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

スライド一覧 はじめに 研究概要 Mathematicaについて 改良点 研究結果 まとめ 参考文献

はじめに 先生に勧められ、かつ1年間熱心に研究できるテーマ だと思い、本研究を行った。

研究概要 VPNの下でのストリーミング配信の劣化 劣化 VPN

NG OK 仮定 ストリーミングの本数増加 ストリーミング配信をキャンセルする確率 Max 0 1 2 3 el el+1 el+2 el+3 n ストリーミングの本数増加 ストリーミング配信サービスの劣化

プログラム内容 第二固有値 緩和時間 ストリーミングの本数 α:増加する確率 β:減少する確率 固有値計算 確率行列 (三重対角行列) 1 6 5 4 3 2 α β ストリーミングの本数 α:増加する確率 β:減少する確率 第二固有値 固有値計算 緩和時間 確率行列 (三重対角行列)

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[~] 複雑な計算をする組み込み関数の中に組み込み関数を多用すると処理 時間がかかる.  A: SparseArray[Array[~], Rest[~],~]  B: a=Array[~]    b=Rest[~]     SparseArray[a, b,~] プログラムA プログラムB 処理速度(s) 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 } 固有値計算へ   ] 計算処理 メモリ小

研究結果 最大ストリームについて

el(キャンセル率の最大)について ※el=18からメモリ不足により測定不可能

まとめ 処理速度とメモリ量はトレードオフの関係である 同じ計算をする関数でも構造が異なるのでよく検証すること 組み込み関数のみでコーディングするより手続き関数を用 いた方が高速化できる場合がある.

参考文献 Mathematica Document Center 入門Mathematica   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

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