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

Slides:

Advertisements

Similar presentations

Absolute Orientation. Absolute Orientation の問題二つの座標系の間における剛体 (rigid body) 変換を復元する問題である。例えば： 2 台のステレオカメラから得られた３次元情報の間の関係を推定する問題。 2 台のステレオカメラから得られた３次元情報の間の関.

Advertisements

Division of Process Control & Process Systems Engineering Department of Chemical Engineering, Kyoto University

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

1 線形代数学. 2 履修にあたって電子情報システム学科必修 2005 年度１セメスタ開講担当草苅良至（電子情報システム学科）教官室： G I 511 内線： 2095 質問等は上記のいずれかに行なうこと。注意計算用のノートを準備すること。

2. 数値微分法. 数値微分が必要になる場合として、次の 2 つが考えられる。関数が与えられていて、その微分を近似的に計算する。（数値微分の精度が十分で、かつ、計算速度が数値微分の方が早い場合など。）離散的な点の上で離散的なデータしかわかっていない関数の微分を近似的に計算する。（偏微分方程式の数値解を求めたい時.

陰関数定理と比較静学モデルの連立方程式体系で表されるときパラメータが変化したとき如何に変数が変化するか至るところに出てくる.

Computational Fluid Dynamics(CFD) 岡永博夫

遺伝的アルゴリズムにおけるランドスケープによる問題のクラス分類

MPIを用いたグラフの並列計算情報論理工学研究室藤本　涼一.

高精度画像マッチングを用いた SAR衛星画像からの地表変位推定

有限差分法による時間発展問題の解法の基礎

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

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

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

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

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

Fortran と有限差分法の入門の入門の…

ラベル付き区間グラフを列挙するBDDとその応用

全体ミーティング (4/25) 村田雅之.

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

局所探索に基づく原子炉燃料装荷パターンの最適化

4.3　連立１次方程式　　Ax = b 　 (23) と書くことができる。

スペクトル法による数値計算の原理 -一次元線形・非線形移流問題の場合-

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

時空間データからのオブジェクトベース知識発見

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

東京工業大学機械制御システム専攻山北昌毅

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

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

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

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

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

計算アルゴリズム計算理工学専攻　張研究室山本有作.

MPIによる行列積計算情報論理工学研究室渡邉伊織情報論理工学研究室渡邉伊織です。

応用数学計算理工学専攻　杉原研究室山本有作.

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

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

スペクトル法の一部の基礎の初歩へのはじめの一歩

確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究

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

仮想メモリを用いた VMマイグレーションの高速化

確率的学習アルゴリズムを用いた有限状態オートマトンの抽出に関する研究

仮想計算機を用いたサーバ統合における高速なリブートリカバリ

デザイン情報学科メディア情報設計河原英紀

システム制御基礎論システム工学科2年後期.

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

通信機構合わせた最適化をおこなう並列化ンパイラ

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

連続領域におけるファジィ制約充足問題の反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.

未使用メモリに着目した複数ホストにまたがる仮想マシンの高速化

GPUを用いた疎行列の格納形式による行列ベクトル積の評価

適応的近傍を持つシミュレーテッドアニーリングの性能

知識科学研究科知識システム構築論講座林研究室佛明智

「データ学習アルゴリズム」第3章複雑な学習モデル報告者佐々木稔 2003年6月25日 3.1 関数近似モデル

Wavelet係数の局所テクスチャ特徴量を用いたGraph Cutsによる画像セグメンテーション

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

第3章　線形回帰モデル修士1年山田　孝太郎.

秘匿リストマッチングプロトコルとその応用

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

情報科学第６回　数値解析(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日名古屋大学　計算理工学専攻山本有作日立製作所の山本有作です。「～」について発表いたします。

パターン認識特論ｶｰﾈﾙ主成分分析和田俊和.

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

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

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

Presentation transcript:

Finger patternのブロック化による陰的wavelet近似逆行列前処理の高速化今倉　暁　　曽我部　知広　　張　紹良名古屋大学　大学院工学研究科　計算理工学専攻

Outline 近似逆行列前処理 Wavelet近似逆行列前処理 Finger patternのブロック化 [提案法] 数値実験・結果まとめ・今後の課題

近似逆行列前処理

近似逆行列前処理偏微分方程式を離散化した際の線形方程式を前処理付きKrylov部分空間法で解くことを考える. 本研究では, 前処理として以下の近似逆行列前処理を扱う. M の計算. 最小二乗問題完全独立・並列化が容易：M の j 番目の列ベクトル： I の j 番目の列ベクトル

M の非零構造を考える. → A-1の構造を参考にする. 近似逆行列前処理実際に解く上で, M に要求される性質疎行列である. 　　　　　　が小さい. ・・・計算コスト・・・近似逆行列の精度 M の非零構造を考える. → A-1の構造を参考にする. 疎性と精度を両立させたいフィルタリングを行う閾値　：　小閾値　：　大値値大小大小疎性　：　× 精度　：　○ 疎性　：　○ 精度　：　×

Wavelet近似逆行列前処理

Wavelet近似逆行列前処理～離散wavelet変換（DWT）～ L : 任意パラメータ Wの非零構造 4 L = 2 L = 1

Wavelet近似逆行列前処理 W 同値疎性と精度の両立が可能 Finger pattern Finger pattern (S. C. Hawkins and K. Chen, 2006) Finger pattern (T. F. Chan et al., 1997) 同値 W 疎性と精度の両立が可能

Wavelet近似逆行列前処理近似逆行列前処理 Finger pattern 陰的wavelet近似逆行列前処理

Wavelet近似逆行列前処理～wavelet依存性～ DWTの精度に影響近似逆行列の疎性に影響 1.2 116 128 0.4 Time[s] 近似逆行列の疎性に影響 Watt 1 (n=1856) 1.2 116 128 Sherman 4 (n=1104) 0.4 前処理行列の構築時間反復法にかかる時間影響が少ない Daubechies 4 精度が高い疎性が低い計算コストが高い本研究では WaveletをHaarに限定する Haar 精度が低い疎性が高い計算コストが低い反復回数 85 87 Daubechies4 Haar

Finger patternのブロック化

Finger patternのブロック化～従来法の問題点～近似逆行列の計算問題点近似逆行列の非零構造が　　近似逆行列の非零構造が　　列ごとに異なる為, 異なる　　部分行列に対して, QR分解　　を合計n 回行う必要がある. 陰的法を例に・・・最小二乗問題 QR分解の結果を再利用する為に, Finger patternのブロック化を提案する. 本研究では, 陰的法に対してブロック化を行った. QR分解後退代入

Finger patternのブロック化従来法提案法 A(:,Sj) mj(Sj) A(:,Sj) mj(Sj)

Finger patternのブロック化～精度比較～の非零構造 Theorem 1. Proof. 従来法　　提案法

数値実験・結果

数値実験 Test行列 Poisson3Da (electromagnetics problem) 前処理 dw8192 (computational fluid dynamics problem) n = 13514, Nnz = 352726 n = 8192, Nnz = 41746 T b = (1,…,1) 前処理陰的wavelet近似逆行列前処理[従来法] 提案法 ILU(0) 解法 GMRES 初期近似解停止条件 T x = (0,…,0) |r |/|r | < 10 -8 n 計算環境 CPU : PowerPC G5 2.5GHz メモリ : 4.0GB コード : Fortran77 コンパイラ : g77　–O5

結果 poisson3Da QR分解後退代入 ILU(0)の分解 GMRES 12 Time[s] 3.5倍 3.0倍 2.2倍 1.8倍反復回数 158　 158 159　 159 160　 160 57 Time[s] 3.5倍 3.0倍 2.2倍 1.8倍 1.7倍 1.5倍 L= 3 4 5 従来法　提案法従来法　提案法従来法　提案法 ILU(0)

結果 dw8192 ― 前処理なし ― 従来法 L=8 ― 提案法 L=6 ― 提案法 L=7 ― 提案法 L=8 ― ILU(0) 相対残差 ― 前処理なし ― 従来法　L=8 ― 提案法　L=6 ― 提案法　L=7 ― 提案法　L=8 ― ILU(0) ０反復回数５００

結果 dw8192 QR分解後退代入 ILU(0)の分解 GMRES 25 指数関数的に計算時間が増大指数関数的に計算時間が増大計算時間は減少 Time[s] 449 316 230 449 316 230 484 反復回数０ L= ６７８提案法　　　　　 ILU(0)

まとめ・今後の課題

まとめ・今後の課題陰的wavelet近似逆行列前処理に対して, finger pattern のブロック化を行った. 最小二乗問題でのQR分解の結果を再利用すること　により, 全体で約1.5倍高速化された. また, 従来法では収束しない問題に対しても収束す　る場合もみられた. 提案法は従来法に代わる有効な解法になり得る. 今後の課題前処理行列の構築の更なる高速化アルゴリズムの並列化及び実装