Document

固有値計算のニーズとアルゴリズムについて
宮田考史（名古屋大学）
共同研究者：
李東珍（名古屋大学），山下達也（名古屋大学），
曽我部知広（愛知県立大学），張紹良（名古屋大学）
第 3 回 CMSI 人材育成シンポジウム
「応用数理と計算科学の連携Ⅱ」
2015 年 1 月 15 日大阪大学
目次
 はじめに
• 固有値のニーズ
• ニーズに対応する解法
 本研究で扱うニーズ
• 電子構造計算に現れる固有値問題
• 既存解法の適用
 本研究のアプローチ
 数値実験
• 実問題への適用
 まとめと今後の課題
 +α （反復法について）
2
はじめに
 本研究で扱う問題
• 一般化固有値問題
» 入力：行列
» 出力：固有対
• 固有値はすべて実数
対称，対称正定値
Re.
3
固有値のニーズと解法
領域内部
×
最小
Re.
最大
点近傍
ニーズ
解法
すべて
準直接法（QR，QZ）
最小，最大，点近傍
反復法（Krylov，JD）
領域内部
Sakurai-Sugiura
4
本研究で扱うニーズ
ニーズ
与えられた
に対して 
番目の固有値
Re.
• 必要な固有値は少数
• 最小や最大ではない
» 発光ポリマ
» 金ナノワイヤ
異なるニーズ
 アプローチは？
• 点や領域の指定は困難
5
本研究のアプローチ
 慣性と反復法の組み合わせ
(Step 1) 慣性 & 反復法
(Step 2) 慣性（二分探索）
(Step 3) 反復法
 慣性とは？
与えられた
に対して 
となる
（
の数
の値は分からない）
6個
2個
0個
Re.
6
慣性の利用
0
0
7
2
Re.
Step 1
（後で説明）
Step 2
3
5
慣性（二分探索）
区間内の固有値数
m 個以下
Step 3
反復法（点近傍）
×
7
反復法の利用
Step 1
0
0
Re.
① どこから始める？
② 次の点はどこに？
③ いつかは
を含む？
反復回数
反復法の近似固有値
① 初期近似固有値
② 1 反復後の近似固有値を活用
③ 多くても n 反復で含む
Re.
8
数値実験
• 計算機環境： Intel Xeon 5960 (3.4 GHz）, Fortran 倍精度演算
Step
• 発光ポリマ
解法
計算された固有値（16桁）計算時間（秒）
法a
-0.42587755479569 50
59.1
本研究
-0.42587755479569 62
36.5
QR
a
LAPACK routine (DSYGV)
b
Arnoldi (M,W,G) [Yamashita et al., 2011]
1
反復法b：2
慣性c：2
2
慣性c：4
3
反復法b：86
計算された固有値（16桁）計算時間（秒）
QR 法a
0.13053888359411 69
408
本研究
0.13053888359411 77
256
（秒）
0.2
9.1
18.0
9.1
LAPACK routine (DSYTRF)
Step
• 金ナノワイヤ
解法
c
計算：回数
計算：回数
1
反復法b：2
慣性c：2
2
慣性c：4
3
反復法b：52
（秒）
1
66
132
57
9
まとめと今後の課題
 まとめ
• 電子構造計算に現れる固有値問題に対して
» 固有値のニーズを整理（k 番目の固有値）
» 慣性と反復法を組み合わせたアプローチ
• 数値実験の結果
» 必要な固有値を QR 法よりも少ない計算時間で得られた
 今後の課題
• 慣性計算の高速化（近似計算，GPU の利用）
• 大規模問題への適用と性能評価
10
ここから別の話です
はじめに
 本研究で扱う問題
• 一般化固有値問題
» 入力：行列
» 出力：固有対
固有値固有ベクトル
• 応用分野
» 電子構造解析
» 流体安定性解析
» 振動解析
Bai et al.,
Non-Hermitian
Eigenvalue Problem
Collection
12
固有値計算アルゴリズム
 すべての固有値  （準）直接法 + 並列計算
» QZ 法
[ Moler & Stewart, 1973 ]
 少数の固有値  反復（射影）法
• 絶対値最大，指定された点近傍
» Lanczos 法
» Arnoldi 法
» Arnoldi (M,W,G) 法
[ Lanczos, 1950 ]
[ Arnoldi, 1951 ]
[ Yamashita et al., 2011 ]
• 指定された領域内部
» Sakurai-Sugiura 法
[ Sakurai & Sugiura, 2003 ]
• 指定された絶対値を有する（複素）固有値
» 実問題に対して，Sakurai-Sugiura 法を拡張 [ Miyata et al., 2009 ]
13
概要
正則な大規模疎行列
Arnoldi(M,W,G)法
 従来法
Arnoldi法
[Arnoldi,1951]
Lanczos法
[Lanczos,1950]
任意性を持った 3 つの行列を
導入し，Arnoldi 法を拡張
様々なアルゴリズムの構築を可能にした上で，
高速アルゴリズムの導出を目指す
14
反復法
初期ベクトル
部分空間
の構築
（低次元）部分空間の
基底を生成する
初期ベクトル
近似固有対
の構築
収束判定
部分空間の中で
固有ベクトルを近似する
部分空間
真の固有ベクトル
近似固有ベクトル
15
Arnoldi 法
初期ベクトル
部分空間
の構築
近似固有対
の構築
収束判定
部分空間の構築
▶ Krylov部分空間：
▶ 基底：
▶ 基底の直交性：
固有対不変
16
Arnoldi 法
初期ベクトル
部分空間
の構築
近似固有対
の構築
収束判定
近似固有対の構築
▶ 近似固有ベクトル：
▶ Petrov-Galerkin条件：
（残差ベクトル：
小規模固有値問題に帰着：
）
（
：ヘッセンベルグ行列）
行列
17
Arnoldi 法の拡張
 行列
（
部分空間の構築
に任意性を与え，Arnoldi法を拡張
：正則，
：正定値エルミート）
Arnoldi(M,W,G) 法
▶ 部分空間：
▶ 基底の直交性：
近似固有対の構築
▶ 残差条件：
▶ 小規模固有値問題：
のとき，
18
M,W,G の設定
▶ 部分空間
を定める行列
▶ 従来法では，基底生成毎に
に着目
or
の計算が必要
Arnoldi(M,W,G) 法
 線形方程式を直接法で解く
Arnoldi法
▶ LU分解
Lanczos法
▶ Cholesky分解
 逆行列（
解法 a
 ベクトル（
）の近似
▶ Neumann級数展開
）の近似
解法 b
▶ Krylov部分空間法
解法 c
▶ 定常反復法
19
テスト問題
問題 1 （電子構造解析）
行列 A
7,776
3,619,104
行列 B
7,776
3,619,104
▶
: 行列サイズ
▶
: 非零要素数
非
零
構
造
（A: エルミート，B: 正定値エルミート）
問題 2 （電気工学）
問題 3 （乱数行列）
行列 A
782
7,514
行列 B
782
5,982
非
零
構
造
行列 A
8,000
12,800,000
行列 B
8,000
12,800,000
非
零
構
造
実験結果（計算時間）
問題 1
▶ 実用的な解法として
有効に機能する可能性あり
従来法（行列分解）
従来法（その他）
Krylov部分空間法を用いた解法
（行列の不完全分解）
Krylov部分空間法を用いた解法
（その他）
計
算
時
間
（
秒
）
問題 2
計
算
時
間
（
秒
）
問題 3
計
算
時
間
（
秒
）
21
まとめと今後の課題
 まとめ
• 一般化固有値問題に対する Arnoldi(M,W,G) 法
» Lanczos 法，Arnoldi 法の拡張
» M に着目  具体的な解法の導出
• 数値実験の結果
» 導出した解法の一部について，その有効性を確認
 今後の課題
• 他の解法の導出
• ブロック化の導入
22

Download Report