,.'+05,.4ア
アルゴリズムによる連立一次方程式の求解高速化

多田野寛人
筑波大学大学院システム情報工学研究科
新学術領域研究「コンピューティクスによる物質デザイン」
平成 年度研究会
年 月 日本研究の背景
7はじめにはじめに大規模固有値問題
  

：固有値， ：固有ベクトル"%+30%*"3)*30%法
複素平面上の指定した領域内の複素平面上の指定した領域内の指定固有対を求めることができる "%+30%*"3)*30%法の計算の主要部
                 の求解
連立一次方程式：
連立一次方程式： の求解              
ここで，
ここで，
「コンピューティクスによる物質デザイン」平成

年度研究会

年 月 日

本研究の背景と目的
7はじめにはじめに"%+30%*"3)*30%法の特長
・複数の連立一次方程式は，互いに独立に求解が可能
・複数の連立一次方程式は，互いに独立に求解が可能
・十分な計算資源があれば，全て同時に解くことができる

複数右辺ベクトルをもつ連立一次方程式の
求解時間の短縮が重要！

目的
複数右辺ベクトルをもつ連立一次方程式の求解高速化
「コンピューティクスによる物質デザイン」平成年度研究会

年 月 日

 

,.'+05,.4部
部分空間反復法の特長
7 ,.'+05,.4部分空間反復法
, +  , 部
部分空間反復法

連立一次方程式           

,.'+05,.4部分空間反復法で解く
 本の方程式をまとめて解くことができる
本の方程式をまとめて解くことができる
 本ずつ05,.4部分空間反復法で解いた場合よりも本ずつ 05,.4 部分空間反復法で解いた場合よりも少ない反復回数で解が得られることがある
少ない反復回数で解が得られることがある得 右辺ベクトル数が大きくなると，数値的に不安定な
右辺ベクトル数が大きくなると，数値的に不安定な状況に陥ることがある．
状況に陥ることがある．
「コンピューティクスによる物質デザイン」平成年度研究会

年 月 日

 

,.'+*"#法の残差の振る舞い
7 ,.'+05,.4部分空間反復法
, +  , 部分
分空間反復法   


  

*),.'+*"#法の相対残差履歴．
．■：，■： ，■： ，■： ，■：．
「コンピューティクスによる物質デザイン」平成年度研究会

年 月 日

 

,.'+*"#法の不安定性の原因
                                                                      
                             





                     

7 ,.'+05,.4部分空間反復法
, +  , 部分
分空間反復法 反復過程で 本のベクトルの線形独立性が失われてくる．
  を求めるための小規模方程式が悪条件問題になり，求解時に誤差が混入する．

改良案
小規模方程式の係数行列に方程式 係含まれる の独立性を回復させる．

「コンピューティクスによる物質デザイン」平成年度研究会

年 月 日

 

,.'+*"#法
法の安定化       
                                       

7 ,.'+05,.4部
部分空間反復法                         ・行列  を直交化し  を生成．
     
反復の中では を用いて計算．
            ・数値的不安定性の原因となる               は，計算途中で一切現れない！
                                                       直交化による,.'+*"#法の安定化
7 ,.'+05,.4部分空間反復法
, +  , 部分空空間反復法        %,.'+*"#  

&直交化付き,.'+*"#*) ,.'+*"#法と直交化付き版の相対残差履歴．
■：，■： ，■： ，■： ，■：．
「コンピューティクスによる物質デザイン」平成年度研究会

年 月 日

,.'+版における行列・ベクトル積の高速化
7 ,.'+05,.4部分空間反復法
, +  , 部分空間間反復法
・行列は !"形式で格納・を計算．は 行 列の配列

        



問題点・についてメモリの連続アクセスが出来ていない・行列データを回読まなければならない「コンピューティクスによる物質デザイン」平成年度研究会

年 月 日

,.'+版における行列・ベクトル積の高速化
7 ,.'+05,.4部分空間反復法
, +  , 部分空間間反復法【解決策】→ 行列 を転置した形で保持する        


・について（少なくとも 回は）連続アクセスができる．
・行列データは 回しか読み込まない．
・についても連続アクセスが保たれている．
「コンピューティクスによる物質デザイン」平成年度研究会

年 月 日

,.'+版
版における行列・ベクトル積の高速化






















)"&$& (#' '&#($%!%&$&"#*)  右辺ベクトル数の変化に対する行列・ベクトル積の"値，
ピーク性能比の変化．
テスト行列として，格子 計算で現れる行列    ，--6   を用いた．
実験環境は，# #13+3&%ののノード．
$/2(0.-  6 ，/(-で 並列で計算．

解く連立一次方程式
7 数値実験
数値実験解く問題
格子量子色力学（ ）計算で現れる
連立一次方程式：  
   ，--6   ，行あたりの非零要素数は ．

*)  非零構造図．
 解法の収束性を向上させるために，前処理として
%'.&*法を用いた（ %'.&*法の反復回数を とする ）．
 右辺ベクトル数と，%'.&*法の反復回数を変化させ，
反復回数，及び計算時間の変化を調べる．
「コンピューティクスによる物質デザイン」平成年度研究会

年 月 日

実験環境と実験条件
7 数値実験
数値実験#%&,(実験環境（# #13+3&%ノード）．
          !# !  "!              #%&,( 実験条件．
                                       

「コンピューティクスによる物質デザイン」平成年度研究会

年 月 日

 

ブロック数と前処理の変化による反復回数の変化
7 数値実験
数値実実験  
     *)  右辺ベクトル数 と %'.&*法の反復回数 の変化による
直交化付き ,.'+*"#法の反復回数の変化．
●：，●： ， ●： ，●： ，●：，●：，●： ．
「コンピューティクスによる物質デザイン」平成

年度研究会

年 月 日

 

ブロック数と前処理の変化による計算時間の変化
7 数値実験
数値実実験 

     *)  右辺ベクトル数 と %'.&*法の反復回数 の変化による
直交化付き ,.'+*"#法の計算時間の変化．
●：，●： ， ●： ，●： ，●：，●：，●： ．
「コンピューティクスによる物質デザイン」平成

年度研究会

年 月 日

  複
複数右辺ベクトルをもつ連立一次方程式の解法である法の数値的不安定性を抑制した．
,.'+*"#法 ,.'+05,.4ア
アルゴリズムによる高速化と，行列・ベクトル積の高速化の相乗効果により，本の方程式
を解く時間よりも，複数本の方程式を解く時間の方が高速であるケースがあった．

さらに収束性のよい ,.'+05,.4アルゴリズムの構築