PCクラスタ上での 連立一次方程式の解の精度保証

Slides:



Advertisements
Similar presentations
1 広島大学 理学研究科 尾崎 裕介 石川 健一. 1. Graphic Processing Unit (GPU) とは? 2. Nvidia CUDA programming model 3. GPU の高速化 4. QCD with CUDA 5. 結果 6. まとめ 2.
Advertisements

Absolute Orientation. Absolute Orientation の問題 二つの座標系の間における剛体 (rigid body) 変換を復元す る問題である。 例えば: 2 台のステレオカメラから得られた3次元情報の間の関 係を推定する問題。 2 台のステレオカメラから得られた3次元情報の間の関.
大規模な三角 Toeplitz 線形方 程式の高速解法とその応用 ○ 安村 修一(法政大学 4 年) 李 磊(法政大学) 日本応用数理学会「行列・固有値の解法とその応用」研究部会 第6回研究会.
1 線形代数学. 2 履修にあたって 電子情報システム学科 必修 2005 年度1セメスタ開講 担当 草苅良至 (電子情報システム学科) 教官室: G I 511 内線: 2095 質問等は上記のいずれかに行なうこと。 注意計算用のノートを準備すること。
Computational Fluid Dynamics(CFD) 岡永 博夫
MPIを用いたグラフの並列計算 情報論理工学研究室 藤本 涼一.
CPUとGPUの 性能比較 -行列計算およびN体問題を用いて-
計算理工学基礎 「ハイパフォーマンスコンピューティングの基礎」
Fill-in LevelつきIC分解による 前処理について
A Q R QR分解とは? → × ◆QR分解 QTQ = I (単位行列) ◆応用例 ◆主な計算方法 n m 今回はこの方法に注目
Problem J Tile Puzzle 原案:野田 担当:平野,吉田,泉,松本.
三重対角化アルゴリズムの性能評価 早戸拓也・廣田悠輔.
超並列計算研究会 PCクラスタにおける ベンチマークと並列ツールの紹介 廣安 知之 三木 光範 大向 一輝 吉田 純一.
研究集会 「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日 完全パイプライン化シフト QR 法による 実対称三重対角行列の 固有値並列計算 宮田 考史  山本 有作  張 紹良   名古屋大学 大学院工学研究科 計算理工学専攻.
Finger patternのブロック化による 陰的wavelet近似逆行列前処理の 高速化
3 二次方程式 1章 二次方程式 §2 二次方程式と因数分解         (3時間).
4.3 連立1次方程式   Ax = b   (23) と書くことができる。
PCクラスタにおける2個体分散遺伝的アルゴリズムの高速化
スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-
対角マトリックスを用いた3次元剛塑性有限要素法の並列計算 対角マトリックスを用いた剛塑性有限要素法
重力3体問題の数値積分Integration of 3-body encounter.
Nonrigid Structure from Motion in Trajectory Space
P,Q比が変更可能なScaLAPACKの コスト見積もり関数の開発
分散遺伝的アルゴリズムによる各種クラスタのベンチマーク
各種PC クラスタの性能評価 同志社大学 工学部 廣安 知之 三木 光範 谷村 勇輔.
整数計画法を用いた ペグソリティアの解法 ver. 2.1
IT入門B2 ー 連立一次方程式 ー.
線形代数学 4.行列式 吉村 裕一.
半正定値計画問題に対する 行列補完理論の高速実装
理学部情報科学科 金田研究室 指導教官 金田 康正 工藤 誠
応用数理工学特論 線形計算と ハイパフォーマンスコンピューティング
応用数理工学特論 第5回 計算理工学専攻 張研究室 山本有作.
正方行列向け特異値分解の CUDAによる高速化
応用数理工学特論 線形計算と ハイパフォーマンスコンピューティング
MPIによる行列積計算 情報論理工学研究室 渡邉伊織 情報論理工学研究室 渡邉伊織です。
文献名 “Performance Tuning of a CFD Code on the Earth Simulator”
数学 ---> 抽象化、一般化 より複雑な関係ー>解析学 一次関数 y=ax+b より多くの要素ー>線形代数 x y f(x) y1 x1
大阪市立大学 学術情報総合センター 大西克実
応用数理工学特論 第6回 計算理工学専攻 張研究室 山本有作.
スペクトル法の一部の基礎の初歩への はじめの一歩
タップ長が一般化された 適応フィルタの統計力学
MPIとOpenMPを用いた Nクイーン問題の並列化
東京海洋大産学官連携研究員/技術コンサルタント 高須 知二 Tomoji TAKASU
制約条件付問題より生じる 線形方程式反復解法 の 理論的な諸問題について
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(NlogN)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似法
プログラミング演習I 行列計算と線形方程式の求解
LU分解を用いた連立一次方程式.
「R入門」  5.7 行列に対する諸機能  10月23日 (木) 発表者 大城亜里沙.
システム制御基礎論 システム工学科2年後期.
知能システム論I(13) 行列の演算と応用(Matrix) 2008.7.8.
導電性高分子材料の電子状態計算に現れる連立一次方程式に対する 並列直接解法の高性能化
パターン認識特論 担当:和田 俊和 部屋 A513 主成分分析
GPUを用いた疎行列の格納形式による行列ベクトル積の評価
プロセスデータ解析学5 -主成分分析- 担当:長谷部伸治     金 尚弘.
7.一次元ダクトの消音制御系における低コスト化
目的:高速QR分解ルーチンのGPUクラスタ実装
Peer-to-Peerシステムにおける動的な木構造の生成による検索の高速化
P4 通信システム P4.1 ディジタルフィルタの設計とその応用 P4.2 伝送線路のFDTD解析 P4.2 H4.1 P4.1 H4.1
ガウス分布における ベーテ近似の理論解析 東京工業大学総合理工学研究科 知能システム科学専攻 渡辺研究室    西山 悠, 渡辺澄夫.
Jh NAHI 横田 理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景  H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(Nlog2N)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似
メモリ使用量の少ないGCR法の提案 東京大学理学部情報科学科 工藤 誠 東京大学情報基盤センター 黒田 久泰
理工学部情報学科 情報論理工学研究室 延山 周平
目で見る一次変換 河合塾 数学科 生越茂樹 オゴセ シゲキ.
密行列固有値解法の最近の発展 (I) - Multiple Relatively Robust Representation アルゴリズム - 2004年11月26日 名古屋大学 計算理工学専攻 山本有作 日立製作所の山本有作です。 「~」について発表いたします。
パターン認識特論 カーネル主成分分析 和田俊和.
長方行列向け特異値分解の 浮動小数点コプロセッサによる 高速化
応用数理工学特論 線形計算と ハイパフォーマンスコンピューティング
3 一次関数 1章 一次関数とグラフ §4 方程式とグラフ         (3時間).
分散メモリ型並列計算機上での行列演算の並列化
2008年 7月17日 応用数理工学特論 期末発表 鈴木綾華,程飛
Presentation transcript:

PCクラスタ上での 連立一次方程式の解の精度保証 大石進一,荻田 武史(早稲田大学)

概要 分散並列計算環境(PCクラスタ)において 連立一次方程式の数値解の精度保証を行う 並列計算用の数値計算ライブラリScaLAPACKを用いる 大規模な問題(行列サイズ:最大1万次元)で高速かつシャープに精度保証する 現状での問題点と解決に向けて

PC: LAPACK(BLAS, ATLAS) スーパーコン: LAPACK, ScaLAPACK 線形問題 非線形問題 固有値問題 連立一次方程式 密行列 疎行列 高速・安定な数値計算ライブラリ PC: LAPACK(BLAS, ATLAS) スーパーコン: LAPACK, ScaLAPACK PCクラスタ: ScaLAPACK(MPI, PVM)

ScaLAPACKの構成 ScaLAPACK PBLAS LAPACK BLACS BLAS MPI, PVM ATLAS Global Local LAPACK BLACS BLAS MPI, PVM ATLAS

連立一次方程式と精度保証(1) : 倍精度浮動小数点数の集合 に対し を解く

連立一次方程式と精度保証(2) [1] S. Oishi and S. Rump (2000) [2] T. Ogita, S. Oishi and Y. Ushiro (2001)

LU分解を利用した精度保証 のとき, ならば LU分解の結果を利用して 上限 を高速に計算 なら精度保証可能

数値実験 目的 コンピュータ環境 行列乗算(PDGEMM)の性能評価 連立一次方程式の数値解の精度保証 PC (Pentium III 800MHz, Memory 256MB) 最大64台,LAN接続(Gigabit ether)

行列乗算(PDGEMM) : 10000×10000 のランダム行列 を計算 PDGEMM(PBLAS)を使用 DGEMM(BLAS)はATLASで高速化

行列乗算(PDGEMM)の性能

連立一次方程式の精度保証 係数行列の次元数: 100~10000 数値解の計算: PDGESV(ScaLAPACK) 数値解の精度保証: LU分解を用いた高速精度保証法

連立一次方程式の数値解の精度保証 行列サイズ 数値解の 計算時間 精度保証に要した時間 保証相対精度 100 0.76 0.34 1.5E-12 500 3.89 1.4E-10 1000 8.29 1.90 1.9E-09 5000 55.14 34.80 1.3E-07 10000 182.53 169.70

LU分解を用いた の上限 の計算 行列サイズ 保証相対精度 100 1.3E-08 1.5E-12 500 2.6E-05 1.4E-10 1000 1.2E-03 1.9E-09 5000 0.5 1.3E-07 10000 12.6 (>1)

参考文献 1) S. Oishi, S. Rump: Fast Verification of Solutions of Matrix Equations, Numer. Math., to appear (2001) 2) ScaLAPACK HomePage: http://www.netlib.org/scalapack/ 3) ScaLAPACK Tutorial(日本語版) http://phase.etl.go.jp/phase/lapack-j/ScaLAPACK/