A Q R QR分解とは？ → × ◆QR分解 QTQ = I （単位行列） ◆応用例 ◆主な計算方法 n m 今回はこの方法に注目

Slides:

Advertisements

Similar presentations

画像処理・実習第十四回：パターン認識東海大学情報理工学部情報メディア学科濱本和彦. 今回の内容 5. パターン認識 5.1 マッチングの原理 5.2 テンプレートマッチング実習相互相関とテンプレートマッチング.

Advertisements

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

HBSP モデル上での行列積を求めるアルゴリム情報論理工学吉岡健太.

大規模な三角 Toeplitz 線形方程式の高速解法とその応用 ○ 安村修一（法政大学 4 年）李磊（法政大学）日本応用数理学会「行列・固有値の解法とその応用」研究部会第６回研究会.

Level-3 BLASに基づく特異値分解アルゴリズムのSMP上での性能

CPUとGPUの性能比較－行列計算およびN体問題を用いて－

計算理工学基礎「ハイパフォーマンスコンピューティングの基礎」

※ 対称密行列の固有値分解は特異値分解と共通点が多い

Fill-in LevelつきIC分解による前処理について

点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上

HOG特徴に基づく単眼画像からの人体3次元姿勢推定

一般化Bi-CGSTAB(s, L) (=一般化IDR(s, L))

MATLAB測位プログラミングの基礎とGT (3)

三重対角化アルゴリズムの性能評価早戸拓也・廣田悠輔.

研究集会「超大規模行列の数理的諸問題とその高速解法」 2007 年 3 月 7 日完全パイプライン化シフト QR 法による実対称三重対角行列の固有値並列計算宮田考史　　山本有作　　張紹良　名古屋大学　大学院工学研究科　計算理工学専攻.

Finger patternのブロック化による陰的wavelet近似逆行列前処理の高速化

AllReduce アルゴリズムによる QR 分解の精度について

２. 共有メモリ型並列計算機での特異値分解の高速化

P,Q比が変更可能なScaLAPACKのコスト見積もり関数の開発

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

ランダムプロジェクションを用いた音声特徴量変換

応用数理工学特論線形計算とハイパフォーマンスコンピューティング

ワイヤレス通信におけるMIMO伝送技術.

半正定値計画問題に対する行列補完理論の高速実装

理学部情報科学科金田研究室指導教官金田康正工藤誠

応用数理工学特論線形計算とハイパフォーマンスコンピューティング

応用数理工学特論線形計算とハイパフォーマンスコンピューティング

応用数理工学特論　第5回計算理工学専攻　張研究室山本有作.

応用数理工学特論線形計算とハイパフォーマンスコンピューティング

シミュレーション演習 G. 総合演習（Mathematica演習）システム創成情報工学科

正方行列向け特異値分解の CUDAによる高速化

応用数理工学特論線形計算とハイパフォーマンスコンピューティング

応用数理工学特論期末発表西口健太郎渡邉崇充

高次元データの解析－平均ベクトルに関する検定統計量の漸近分布に対する共分散構造の影響－

非対称行列向けマルチシフトQR法の性能予測方式

応用数理工学特論　第6回計算理工学専攻　張研究室山本有作.

高速剰余算アルゴリズムとそのハードウェア実装についての研究

Level-3 BLASに基づく二重対角化アルゴリズムとその性能評価

東京海洋大産学官連携研究員/技術コンサルタント高須知二 Tomoji TAKASU

Jh NAHI 横田　理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景　H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(NlogN)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似法

確率伝搬法と量子系の平均場理論田中和之東北大学大学院情報科学研究科

「R入門」　　5.7　行列に対する諸機能　 10月23日　(木) 発表者　大城亜里沙.

独立成分分析 (ＩＣＡ：Independent Component Analysis )

トーリックイデアルのグレブナ基底を求めるアルゴリズム – F4およびF5 –

知能システム論Ｉ（１３）行列の演算と応用(Matrix) ２００８．７．８.

導電性高分子材料の電子状態計算に現れる連立一次方程式に対する並列直接解法の高性能化

変換されても変換されない頑固ベクトルどうしたら頑固になれるか頑固なベクトルは何に使える？

パターン認識特論担当：和田俊和部屋 A513 主成分分析

目的：高速QR分解ルーチンのGPUクラスタ実装

Bottom-UpとTop-Down アプローチの組み合わせによる単眼画像からの人体3次元姿勢推定

わかりやすいパターン認識第７章：部分空間法　7.1　部分空間法の基本　7.2　ＣＬＡＦＩＣ法　　　　　　　　　　　　　　　　　６月13日（金）　　　　　　　　　　　　　　　　　大城　亜里沙.

B03 量子論理回路の最適化に関する研究西野哲朗，垂井淳，太田和夫，國廣昇電気通信大学　情報通信工学科.

「ＩＣＡによる顔画像特徴量抽出とＳＶＭを用いた表情認識」

8方向補間ブロックマッチングの実装福永研究室数理科学コース　学部４年　能城　真幸.

Jh NAHI 横田　理央 (東京工業大学) Hierarchical low-rank approximation methods on distributed memory and GPUs 背景　H行列、H2行列、HSS行列などの階層的低ランク近似法はO(N2)の要素を持つ密行列をO(N)の要素を持つ行列に圧縮することができる。圧縮された行列を用いることで、行列積、LU分解、固有値計算をO(Nlog2N)で行うことができるため、従来密行列の解法が用いられてきた分野では階層的低ランク近似

メモリ使用量の少ないGCR法の提案東京大学理学部情報科学科工藤誠東京大学情報基盤センター黒田久泰

表紙分散遺伝的アルゴリズムのための新しい交叉法.

１ーQー１８音声特徴量抽出のための音素部分空間統合法の検討

行列一次変換，とくに直交変換.

制約付き非負行列因子分解を用いた音声特徴抽出の検討

実験計画法 Design of Experiments (DoE)

密行列固有値解法の最近の発展 (I) －　Multiple Relatively Robust Representation アルゴリズム　－ 2004年11月26日名古屋大学　計算理工学専攻山本有作日立製作所の山本有作です。「～」について発表いたします。

キャッシュマシン向け三重対角化アルゴリズムの性能予測方式

長方行列向け特異値分解の浮動小数点コプロセッサによる高速化

密行列固有値解法の最近の発展（II）ーマルチシフトQR法ー

目次はじめに収束性理論解析数値実験まとめ特異値計算のための dqds 法シフトによる収束の加速

MPIを用いた並列処理情報論理工学研究室 06‐1‐037‐0246　杉所　拓也.

分散メモリ型並列計算機上での行列演算の並列化

ランダムプロジェクションを用いた音響モデルの線形変換

2008年 7月17日応用数理工学特論期末発表鈴木綾華,程飛

Presentation transcript:

QR分解のブロック化２００８年　７月１０日応用数理工学特論　期末発表深谷　猛

A Q R QR分解とは？ → × ◆QR分解 QTQ = I （単位行列） ◆応用例 ◆主な計算方法 n m 今回はこの方法に注目（直交行列）（上三角行列） QTQ = I （単位行列） ◆応用例最小二乗問題長方行列の特異値分解三重対角化（二重対角化）のブロックアルゴリズム ◆主な計算方法グラム・シュミットの直交化ハウスホルダー変換今回はこの方法に注目

ハウスホルダー変換によるQR分解 ◆ハウスホルダー変換（直交行列） ◆QR分解への適用 → → → （直交行列の積⇒直交行列） →

ハウスホルダーQR分解の問題点両方ともLevel-2 BLAS Level-3 BLASを使うためにブロック化を行う行列ベクトル積：行列ベクトル積：行列のランク１更新：両方ともLevel-2 BLAS データの再利用性が低いため，計算機の性能が出ない Level-3 BLASを使うためにブロック化を行う

ハウスホルダー変換のブロック化 ◆compact-WY representation Y T YT 計算コスト： O(ml 2) ◆Level-3 BLASによるハウスホルダー変換の作用 2l 回のLevel-2 BLAS 3回のLevel-3 BLAS

ハウスホルダーQR分解のブロック化 ◆Fixed-size Blocking （LAPACKで使用されている手法） Level-2 BLAS 1 2 3 → 1 2 3 l （ⅰ）ブロック内のQR分解 → 1 従来（非ブロック化）のアルゴリズム Level-2 BLAS （ⅱ）compact-WY representationの計算 Level-2 BLAS （ⅲ）compact-WY representationの作用 2 3 → Level-3 BLAS

QR分解のブロック化におけるポイント ◆ブロック化による高速化の原理 ◆様々なブロック化方法両者ともブロック幅に依存 Lv.2 全体の計算量は増加（compact-WY representationの計算） WY Lv.3 計算量 Level-3 BLASの部分で時間短縮計算時間両者ともブロック幅に依存 ◆様々なブロック化方法 Variable-size Blocking Recursive Blocking 複数のブロック化方法の組合せ（ハイブリッド型）計算環境や問題サイズに合ったブロック化が望ましい

高速化率 = 非ブロック化での実行時間 / ブロック化での実行時間数値実験について ◆実験方法自作プログラム同士（非ブロック化とブロック化） LAPACKのDGEQR2（非ブロック化）とDGEQRF（ブロック化）それぞれ行列サイズを変えて，QR分解の実行時間を測定（※自作のブロック化プログラムはブロック幅を変化させて測定）高速化率 = 非ブロック化での実行時間 / ブロック化での実行時間 ◆実験環境 CPU ：　Opteron（2.0GHz） BLAS ：　AMD ACML

Level-2 BLASとLevel-3 BLASの性能比較 DGEMV (Level-2 BLAS) ： n × n 行列と n 次元ベクトルの積 DGEMM (Level-3 BLAS) ： n × n 行列と n × n 行列の積 MFLOPS 6～7倍程度の性能差 n

ブロック化による高速化率の評価 ◆自作プログラム ◆LAPACKのルーチン 1000×1000 3.84 0.54 30 7.04 行列サイズ実行時間（秒）高速化率非ブロック化ブロック化ブロック幅 1000×1000 3.84 0.54 30 7.04 3000×1000 22.7 2.43 40 9.33 3000×3000 174 13.4 60 12.96 ◆LAPACKのルーチン行列サイズ実行時間（秒）高速化率非ブロック化（DGEQR2）ブロック化（DGEQRF）ブロック幅 1000×1000 3.13 0.51 ー 6.09 3000×1000 13.3 1.99 6.69 3000×3000 89.8 11.7 7.67

ブロック幅による実行時間の変化実行時間（秒） best ブロック幅行列サイズが小さく，Level-3 BLASの性能がでない（自作プログラムを使用）（サイズ： 3000×1000）行列サイズが小さく，Level-3 BLASの性能がでない best Level-3 BLAS以外の演算量の増加（ブロック内QR分解 & WY representation計算）ブロック幅

行列サイズによる高速化率の変化高速化率 BLASの性能差と同程度行列のサイズ（正方行列）

まとめハウスホルダー変換によるQR分解のブロック化を行った． compact-WY representationを用いてブロック化を行うことで，Level-3 BLASを使うことが可能になった．自作プログラムを用いた数値実験の結果，最大で13倍程度の高速化を確認できた． LAPACKのルーチンを用いた数値実験の結果，BLASの性能差と同程度の高速化率が確認できた．

(補足)QR分解のアルゴリズム ◆non-blocking

(補足)QR分解のアルゴリズム ◆fixed-size blocking