実対称帯行列の固有値問題に対する分割統治法の分割戦略
7
0
0
全文
(2) Vol.2019-HPC-169 No.3 2019/5/10. 情報処理学会研究報告 IPSJ SIG Technical Report ୕㔜ᑐゅ⾜ิ䛾 ᅛ᭷ᑐィ⟬. ୕㔜ᑐゅ. ୕㔜ᑐゅ䛾㏫ኚ. T T 䛾ᅛ᭷䝧䜽䝖䝹. ୕㔜ᑐゅ⾜ิ. A. X ᖏ⾜ิ䛾 ᅛ᭷ᑐィ⟬. k +1 ᐦ⾜ิ. A 䛾ᅛ᭷䝧䜽䝖䝹. B. ᖏ⾜ิ. ᖏ⾜ิ䛾㏫ኚ. ᖏ⾜ิ䠄༙ᖏᖜ k䠅. B 䛾ᅛ᭷䝧䜽䝖䝹. 図 1 密行列固有値問題の求解過程．上側，下側のパスがそれぞれ三重対角行列，帯行列を中 間形とする方法を示す．. 法 [10] に対しても自然な拡張が可能である．. B を以下のように相似変換する．. 本稿の構成を以下に述べる．第 2 節では，帯行列固有値 問題に対する分割統治法について述べる．第 3 節では，帯. r ∑. Y ⊤ BY = D +. (1). [. により提案する分割戦略の有効性を示す．第 5 節では提案. D=. ui. D1 O. まとめと今後の課題について述べる．. (2). = Y ⊤ vi (i = 1, 2, . . . , r), ] [ ] O Y1 O , Y = . D2 O Y2. 次に，対角行列とランク 1 積の和の固有値問題を. 2. 実対称帯行列に対する分割統治法. D + ρ1 u1 (u1 )⊤ = Q1 Λ1 Q⊤ 1 (1). 本節では，実対称帯行列に対する分割統治法（以下，単. (1). と解く．このような対角行列とランク 1 積の和で表さ. に分割統治法）について概説する． 分割統治法による帯行列固有値問題 (1) の求解手順を. れる行列の固有対は比較的容易に求められることが知 られている．その解を用いて (2) の右辺を. 示す．. (i) 行列の分割点 m (k ≤ m ≤ n − k) を適当に選び， [ ] r ∑ B1 O B= + ρi vi vi ⊤ O B2 i=1. Q⊤ 1 [D +. r ∑. (n−m)×(n−m). ，実数 ρi (i = 1, 2, . . . , r)，実ベ. = Λ1 +. (2). ui. 割）．ただし，r は B の第 m − k + 1 行から第 m 行，. r ∑. = Q⊤ 1 ui. (1). ρi ui (ui )⊤ (2). (2). (i = 2, 3, . . . , r).. 同様の固有値問題の求解と相似変換. であり，0 ≤ r ≤ k を満たす．このような問題の分割. Q⊤ q [D +. は k × k 部分行列の特異値分解と若干の計算により求. r ∑. ρi ui (ui )⊤ ]Qq (q). (q). i=q. められる．. (ii) B よりも次数の小さい帯行列 B1 ，B2 の固有値問題. = Λq +. r ∑. (q+1). ρi ui. (q+1) ⊤. (ui. ) ,. i=q+1. （小問題）を解く．すなわち， (q+1). Bj =. (1). とランク 1 積の 1 つ少ない形に相似変換する．ただし，. クトル vi ∈ R (i = 1, 2, . . . , r) を求める（行列の分. Yj Dj Yj⊤. (1). i=2. n. 第 m − k + 1 列から第 m 列の k × k 部分行列のランク. ρi ui (ui )⊤ ]Q1. i=1. を 満 た す 半 帯 幅 k の 実 対 称 帯 行 列 B1 ∈ Rm×m ，. B2 ∈ R. (1). ただし，. 化する 2 つの分割戦略を提案する．第 4 節では，数値実験 する分割戦略に関連する研究について紹介する．最終節で. (1). i=1. 行列固有値問題に対する分割統治法の分割戦略について述 べる．この際，分割統治法の計算量を最小化ならび準最小. ρi ui (ui )⊤ .. ui. (j = 1, 2). = Q⊤ q ui. (q). (i = q + 1, q + 2, . . . , r). を q = 2, 3, . . . , r と繰り返すと，最終的に を満たす直交行列 Y1 , Y2 ，対角行列 D1 , D2 を求める．. (iii) 帯行列 B1 ，B2 の固有値問題の解をもとに，B の固有 値問題の解を求める．r = 0 の場合，B は B1 , B2 から なるブロック対角行列であるので [ ] [ D1 O Y1 Λ= ,X = O D2 O. O. ]. と対角化できる．したがって，B の固有値は Λ = Λr であり，対応する固有ベクトル X は以下の積で求め られる．. [. Y2. が解となる．r ≥ 1 の場合，まず，小問題の解により. c 2019 Information Processing Society of Japan ⃝. [Y Q1 Q2 · · · Qr ]⊤ B[Y Q1 Q2 · · · Qr ] = Λr. X=. Y1. O. O. Y2. ] Q1 Q2 · · · Qr .. (3). 2.
(3) Vol.2019-HPC-169 No.3 2019/5/10. 情報処理学会研究報告 IPSJ SIG Technical Report. ステップ (ii) の小問題の求解は，分割統治法の再帰的適用. フレーションによる次数の削減が少なく，(4) はステッ. により行われる．したがって，分割統治法では，与えられ. プ (iii) の行列積計算量の良い近似となる．. た行列を再帰的に分割して二分木状に小問題を構築し，二. このような仮定をおいたとき，ステップ (i) の計算量 O(k 3 ). 分木の葉から根に向かって小問題を再帰的に解くことで，. は，ステップ (iii) の行列積の計算量 (4) と比べて極めて少. 最終的に B の固有対を求めることになる．. ない．したがって，この仮定の下での分割統治法全体の計. 分割統治法の各ステップの計算量について述べる． ステップ (i) は，分割点 m を定めた後の B1 , B2 ，ρi , vi. (i = 1, 2, . . . , r). を求める計算量がその大部分となる*2 ．こ. れは，非対角部の k × k 部分行列の特異値分解と，その分 解結果を用いた B1 , B2 の計算からなる．diag(B1 , B2 ) は. 算量は，ステップ (iii) の行列積の計算量 (4) と，ステップ. (ii) で B1 ，B2 に対して分割統治法を（再帰的に）適用し たときの計算量の合計だけを考えれば良い． 帯行列 B が特別な性質をもつ場合には，計算量を最小化 するための分割戦略は単純である．具体的には，. B1 の右下 k × k ，B2 の左上 k × k ，そして非対角部の k × k. • ランク r が分割点 m によらず一定である場合，または. 部分行列以外は B と同じ値をもつため，実際には k × k 行. • 半帯幅が k = 1（すなわち B が実対称三重対角行列）. 列同士の密行列積を 2 回行うだけで良い．したがって，ス 3. の場合. テップ (i) の計算量は O(k ) となる．ステップ (iii) は，行. である．前者の場合，単に二等分点 m = n/2 を選択し続. 列積 (3) が計算量の大部分を占める．行列積 (3) の計算量. ければ分割統治法の計算量は最小となる．続いて後者の場. は，デフレーションと呼ばれる処理中の行列の次数削減. 合を考える．三重対角行列 B は. や，デフレーションに応じた行列の乗算順序に依存して変 化する．デフレーションによる次数削減が生じない場合，. B = diag(T1 , T2 , . . . , Tq ). Y1 , Y2 ，Q1 , Q2 , . . . , Qr は密行列となり，B を分割点 m で. と 既 約 な 三 重 対 角 行 列 T1 , T2 , . . . , Tq (q ≥ 1) か ら な. 分割したときの (3) の計算量 g(B, m) は，. るブロック対角行列として表現できる．対角ブロック. g(B, m) = 2[m2 + (n − m)2 ]n + 2(r − 1)n3. (4). T1 , T2 , . . . , Tq に対してそれぞれ分割統治法を適用して固有 対を求めれば，ただちに B の固有対が求まる．既約な三重. となる．また，ステップ (ii) では分割統治法を B1 ，B2 に. 対角行列 T1 , T2 , . . . , Tq に対する分割統治法は，ランクが分. 対して適用して固有対を求めるので，それぞれの小問題を. 割点によらず r = 1 で一定であるので，前者の場合と同様. 解くための計算量が必要となる．. に二等分点を選択し続ければ計算量が最小となる．デファ. 分割点 m の選択は，ステップ (iii) の行列積の計算量 (4). クトスタンダード行列計算ライブラリ LAPACK[11] の三. に影響し，また固有対を求めるべき B1 , B2 も変化する．さ. 重対角行列に対する分割統治法ルーチン DSTEDC ではこ. らに，各小問題で分割点の選択に任意性があり，その選択. の分割戦略が利用されている．. が小問題求解の計算量を変化させる．図 2 に分割統治法に. 一般の帯行列を扱う場合には分割点 m の選択によって. おける再帰的分割の例を 2 つ示す．このような再帰的分割. k × k 部分行列のランク r の値が変化するため，前述の特. を行う方法には膨大な種類があり，どのような分割方法が. 別の場合のような適当な分割戦略が確立されていない．そ. 適当である（より計算量や実行時間を削減する）かは自明. こで，以下の副節では，まず最も自然に思いつかれる二等. ではない．. 分点での分割を繰り返す単純な分割戦略について述べたあ. 3. 分割統治法の分割戦略 分割統治法の分割点の決定方法（分割戦略）について述 べる．以下では，計算量をモデル化するうえで 2 つの仮定 を行う．. と，計算量を削減するための 2 つの分割戦略を提案する．. 3.1 二等分点での分割を繰り返す戦略 本副節では，図 2 (A) のように，常に二等分点を分割点 として選択する分割戦略について述べる．本分割戦略は単. • 半帯幅 k について k ≪ n が成り立つと仮定する．密. 純であるが，m = n/2 とする分割点の選択は，各小問題. 行列固有値問題を帯行列化して解く場合，k ≪ n とな. における (4) の右辺第 1 項を最小化する選択となる．した. るようにするのが普通であり，そのような応用では本. がって，本節の冒頭で述べた特別な場合のように r が常に. 仮定は自然なものである．. 一定の値となるのであれば計算量を最小化できる．しか. • デフレーションによる次元削減が生じないと仮定す. し，一般の場合に分割点 m の選択によって r は 0 ≤ r ≤ k. *2. る．すなわちステップ (iii) の行列積の計算量が (4) の. の範囲で変化するため，一般に (4) の右辺第 2 項の値を小. 通りになると仮定する．分割統治法においてデフレー. さくすることができず，また，小問題の計算量を削減する. ションがまったく生じないのは非常に稀であるが，解. ための有利な分割戦略ともならない．二等分点を選択する. くべき固有値問題の固有値の重複が少ない場合にはデ. 分割戦略で計算量が最悪となるのは，二等分点で分割し続. ここでは分割点 m の決定にかかるコストを考慮していない．. c 2019 Information Processing Society of Japan ⃝. けたときに，常に非対角ブロックのランク r が r = k とな. 3.
(4) Vol.2019-HPC-169 No.3 2019/5/10. 情報処理学会研究報告 IPSJ SIG Technical Report. 䠄㻭䠅. 䠄㻮䠅 r=2. r=2. r=1 r=2. r=1 r=2. 図 2 非対角要素にゼロ（白色）を含む帯行列に対する再帰的分割の例．(A) は分割後の行列 の次数が均等になるように分割点を選択し，(B) はランク r が小さくなるように分割点 を選択している．. る場合であり，そのときの計算量は. 4 (2k − 1)n3 3. かる時間が無視できないほど大きいという欠点がある．そ こで本副節では，候補とする分割点に制限を加えることで，. (5). より短い探索時間で準最適な分割点を決定する分割戦略を 提案する．. となる．. 分割点 m に二等分点 n/2 から遠く離れた点を選択する. 3.2 計算量最小の分割点を求める分割戦略（提案法 1） 本副節では，本節冒頭で述べた仮定の下，計算量を最適 化する再帰的分割を生成する分割戦略を提案する．. と，(4) の右辺第 1 項は大きく増大する．したがって，そ のような点は最適分割点であることは稀であり，また，最 適であっても他の分割点候補と比べて大きく計算量を削減. 帯行列 B に対して計算量を最小化するように再帰的分. することは少ないと推測できる．そこで，二等分点付近の. 割を行ったときの計算量を f (B) とおく．f (B) は，行列積. s 点のみを分割点の候補することを考える．このような制. 計算量 (4) と，最適な分割によって生じた B1 , B2 に最適分. 約のもとで帯行列 B に対して計算量を最小化するように再. 割の分割統治法を適用したときの計算量 f (B1 ), f (B2 ) に よって. 帰的分割を行ったときの分割統治法の計算量 f ′ (B) は，. f ′ (B) = min ′ g(B, m) + f ′ (B1 ) + f ′ (B2 ), m∈M. f (B) = min [g(B, m) + f (B1 ) + f (B2 )] ,. と書ける．したがって，計算量が最小となる再帰的分割の. dim(B) − s dim(B) − s M ′ = {⌊ ⌋ + 1, ⌊ ⌋ + 2, 2 2 dim(B) + s ⌋} ...,⌊ 2. 決定は，最小値 f (B) とそのときの分割点（B の分割点 m. と書ける．したがって，制約下での計算量が最小となる再. および再帰的に生成される小問題の分割点）を求める最小. 帰的分割の決定は，最小値 f ′ (B) とそのときの分割点を求. m∈M. M = {k, k + 1, . . . , dim(B) − k + 1}. 化問題となる．上記の最小化問題は，最小値 f (B) が部分問. める最小化問題となり，第 3.2 副節と同じく，動的計画法. 題の最小値 f (B1 ), f (B2 ) および容易に計算可能な g(B, m). によって比較的効率的に解ける．本副節では，上記の要領. の和として表現されていることから，動的計画法によって. で計算量が f ′ (B) となるように分割点を決定する分割戦略. 比較的効率的に求められる．本副節では，上記の要領で計. を提案する．. 算量が最小（すなわち f (B)）となるように分割点を決定 する分割戦略を提案する．. 本副節で提案する分割戦略の探索回数は O(sn2 ) である． したがって，小さな s を設定すれば探索に必要な時間を大. 本戦略における分割点の決定には，動的計画法により効 3. きく削減できる．当然，探索範囲の制限による探索時間削. 率的な探索を行う場合でも O(n ) 回の探索が必要であり，. 減と，分割統治法の計算量削減はトレードオフの関係にあ. 分割統治法そのものの計算量に比べて無視できないほど大. るため，パラメータ s は適当な値を設定する必要がある．. きいという問題がある．このため，二等分点での分割戦略 に変えて提案分割戦略を採用してり行列積の計算量を大き く削減できたとしても，分割点の探索時間のため，実行時 間全体はかえって増大する可能性がある．. 4. 数値実験 提案する分割戦略（提案法 1，2）を適用した分割統治法 の計算量および分割点探索に要する実行時間を，数値実験 により評価する．. 3.3 準最適な分割点を求める分割戦略（提案法 2） 第 3.2 副節で述べた提案法 1 は，その分割点の決定にか. c 2019 Information Processing Society of Japan ⃝. 本数値実験では，実対称帯行列 B の対角および下三角部 の帯内の各要素を [0, 1) 一様乱数により生成し，その後に. 4.
(5) Vol.2019-HPC-169 No.3 2019/5/10. 情報処理学会研究報告 IPSJ SIG Technical Report. 確率 p で生成した要素をゼロに置き換えることで，テスト メータである．p が大きな値であるほど B の帯内要素のゼ ロ要素の割合が増大し，r < k となる分割点候補が増大す る．したがって，p を大きく設定するほど提案する分割戦 略適用時の計算量削減効果は大きいと予想される． 実験に用いた計算機環境は表 1 の通りである．テストプ ログラムの動的計画法による分割点探索機能は C++11 に より実装し，残りの部分は Fortran 90 により実装した．非 対角ブロックのランク r は，非対角ブロックの特異値のう ち最大特異値の 10−15 倍以上の特異値の数とした．特異値. N )/23V[(4/3)(2k-1)n3]. 行列を人工的に生成する．確率 p は実行時に設定するパラ. N . N . N . . . . . . =HURHOHPHQWSUREDELOLW\p 図 3 二等分点選択時の最悪計算量 (4/3)(2k − 1)n3 に対する，提 案法 1 による最適分割点選択時の計算量（n = 2000）．. の計算には行列計算ライブラリ LAPACK/LAPACKE の. V . トプログラムはスレッド並列化されていない．. . ま ず ，テ ス ト 行 列 を n = 2000，k = 2, 3, 4, 5，p =. 0.005, 0.01, 0.02, 0.04, 0.08 として作成し，提案法 1 によ る最適分割点を用いたときの分割統治法の計算量を評価し た．二等分点を選択し続ける分割統治法の最悪計算量 (5) に対する，最適分割点を用いたときの計算量の比を図 3 に 示す．いずれのテスト行列でも二等分点を選択し続ける場 合と比べて大きく計算量を削減できていることが確認でき る．また，ゼロ要素の生成確率 p が高いほど計算量の削減 率が高いことが確認できる．これは，p が大きいほど非対 角ブロックのランクが小さくなりやすいことを考えれば自. )/23V[(4/3)(2k-1)n3]. 特異値分解ルーチン LAPACKE dgesvd を用いた．本テス. V . V . . . V QN. . . . =HURHOHPHQWSUREDELOLW\p 図 4 二等分点選択時の最悪計算量 (4/3)(2k − 1)n3 に対する，提 案法 1 による最適分割点選択時および提案法 2 による準最適 分割点選択時の計算量（n = 2000, k = 3）．. 然な結果である．また，半帯幅 k が小さいほど計算量の削 減率も高いことが確認できる．この結果は，本実験の行列. を図 5 に示す．提案法 1 による最適分割点の探索時間は長. 生成方法では，r = k − 1 となる分割点候補は生じやすい. く，また O(n3 ) での増大していることが確認できる．この. が，r ≤ k − 2 となる分割点候補が生じにくいことが原因. ことは，計算量を厳密に最小化する最適分割点の探索は分. であると考えらえる．非対角ブロックは，帯行列の最外対. 割統治法の高速化という目的では実用できないことを意味. 角要素を対角要素とする三角行列であるので，帯行列の最. する．一方で，探索範囲を s = 25, 50, 100 と限定する提案. 外対角要素に一つでもゼロ要素が存在すれば特異（すなわ. 法 2 では限定前と比べて探索実行時間は大きく減少し，s. ち r ≤ k − 1）になる．一方，r ≤ k − 2 となるには帯内の. を小さくするほど実行時間は削減される．また，n の増大. ゼロ要素がランクを下げるように固まって生成されなけれ. による実行時間の増大も O(n3 ) より緩やかである．した. ばならないため，r ≤ k − 2 となる分割点候補は r = k − 1. がって，s を適当に小さく制限する提案法 2 を用いること. となる分割点候補と比べて非常にまれにしか生じない．結. で，分割点の探索時間を分割統治法全体の実行時間に対し. 果，k の値が小さいほど計算量の削減効果が大きくなった. て小さく抑えられると考えられる．ただし，前述の実験結. と考えられる． 次に，テスト行列を n = 2000, k = 3 として作成し，提 案法 1 よる最適分割点選択時および提案法 2 で探索範囲を. s = 25, 50, 100 と限定して準最適分割点を選択したときの，. 果（図 4）の通り計算量削減の効果を高めるには大きな s を設定しなければならないため，探索実行時間と計算量の 削減効果はトレードオフの関係にある． 最後に，n = 4000, k = 3, p = 0.02 のテスト行列に対し. 分割統治法の計算量を評価した．二等分点を選択し続ける. て提案法 1 により計算量を最小とする分割点を探索したと. 分割統治法の最悪計算量 (5) に対する，最適分割点および. きの結果を図 6 に示す．最初の分割点として，二等分点か. 準最適分割点を用いたときの計算量の比を図 4 に示す．探. ら大きく外れるがランク r を大きく減らせる点が選択され. 索範囲を限定するほど（s を小さく設定するほど）計算量. ており，その後の分割も二等分点から遠くとも r < k とな. は二等分点選択時の最悪計算量に近づいていき，計算量を. る分割点ばかりが選択されている．この結果は，二等分点. より多く削減するには s を大きくとる必要があるという自. 付近の s 点を探索するという提案法 2 の探索範囲制限より. 然な結果が得られた．. も，二等分点から遠くともランク r の少ない点を積極的に. 最適分割点および準最適分割点の探索に要した実行時間. c 2019 Information Processing Society of Japan ⃝. 探索するのが良い近似探索となることを示唆している．. 5.
(6) Vol.2019-HPC-169 No.3 2019/5/10. 情報処理学会研究報告 IPSJ SIG Technical Report 表 1 性能評価環境. Intel Xeon E5-2630 v4（2.2 GHz，10 コア，20 スレッド，288 GFLOPS）× 2 ソケット. CPU. DDR4，64 GB ×2. 主記憶 コンパイラ. Intel C++ Compiler 19.0.3.199, Intel Fortran Compiler 19.0.3.199. 最適化オプション（C++）. -xCORE-AVX2 -O3 -align array64byte. 最適化オプション（Fortran）. -xCORE-AVX2 -Ofast. BLAS/LAPACK. 6XE
(7) RSWLPL]DWLRQWLPH>VHF@. V . V . Intel Math Kernel Library (MKL) 2019.0.3 [12]. V . ヘッドを考えると，半帯幅が一定値ずつ減少する経由半帯. V QN. 幅の選択が実用的には良いだろうと述べられている．. . 5.2 ブロックハウスホルダ QR 分解アルゴリズムにおけ. . るブロック分割の最適化 ブロックハウスホルダ QR 分解アルゴリズムは，ブロッ. . ク分割の方法によってブロック化のための計算量や基本行. . . . . . 0DWUL[GLPHQVLRQn. 図 5 提案法 1 による最適分割点の探索および提案法 2 による準最 適分割点の探索の実行時間（k = 3, p = 0.02）．. 列計算ルーチンの性能が変化し，結果としてアルゴリズム 全体の実行時間が変化する．深谷らは，再帰的なブロック 分割を二分木によって系統的に捉え，モデル化された実行 時間を最小化する二分木の探索問題を動的計画法で解く ことで最適なブロック分割を決定する手法を提案してい る [14], [15]．. 5. 関連研究 本節では，第 3.2，3.3 節で提案した動的計画法に基づく. 6. まとめと今後の課題. 分割戦略に関連する 2 つの研究について述べる．いずれも. 本稿では，帯行列固有値問題に対する分割統治法の計算. 分割統治法を取り扱ったものではないが，行列計算アルゴ. 量削減について取り扱った．帯行列の再帰的分割における. リズムの性能（計算量または実行時間）をモデル化し，そ. 分割点の選択には任意性があり，その選択によって計算量. の最適化問題を動的計画法によって解くことを議論してい. が変化することを述べた．本稿では，デフレーションによ. る点で本研究と共通点をもつ．. り行列の次数が削減されない場合の行列積の計算量のみに 着目して分割統治法の計算量をモデル化し，その計算量を. 5.1 帯行列変換アルゴリズムにおける経由半帯幅の選択. 削減するための分割点の決定方法（分割戦略）について議. 半帯幅 k1 の実対称帯行列 B (1) が与えらえるときに，. 論した．常に非対角ブロックのランクが一定である特別な. Q⊤ B (1) Q = B (2) ,. QQ⊤ = I. (6). 帯行列や，半帯幅 k = 1 の帯行列（三重対角行列）の場合 には単純な分割戦略が計算量最小となることを述べた．そ. を満たす半帯幅 k2 の実対称帯行列 B (2) を求めるアルゴリ. の後，一般の帯行列に対して計算量最小となる分割点を，. ズム（帯行列の半帯幅変換アルゴリズム）が提案されてい. 動的計画法によって効率的に探索して決定する分割戦略を. る [13]．ただし，. 提案した．また，分割点の決定に要する時間を削減するた. k1 > k2 ≥ 1. (7). である．. め，探索範囲を限定して準最適な分割点を決定する分割戦 略も同時に提案した．数値実験により，提案する分割戦略 が分割統治法の計算量削減に有効であることを示した．. 帯行列の半帯幅変換アルゴリズムは (7) を満たす任意の. 今後の課題としては，提案する分割戦略を適用した分割. 半帯幅の実対称帯行列に対して適用可能であるので，半帯幅. 統治法プログラムの実行時間の評価が挙げられる．分割点. k1 から半帯幅 k2 の帯行列への変換を，半帯幅 d1 , d2 , . . . , dp. の変更は実行される行列積の次数が変化する，すなわち行. (k1 > d1 > d2 > · · · > dp > k2 )（p は任意の非負整数）の. 列積実行性能が変化する．したがって，計算量の削減が必. 帯行列を経由して行うことが可能である．文献 [13] では，. ず実行時間の削減に一致するとは限らない．また，本研究. 計算量を最小化する経由半帯幅が動的計画法によって効率. ではデフレーションによる行列次数の削減が生じないこと. 的に求められることが述べられている．ただし，半帯幅が. を仮定して計算量をモデル化したが，実際の分割統治法で. 一定値ずつ減少するように経由半帯幅を選択したとして. はデフレーションによる行列次数の削減効果が計算量や実. も，その計算量は最適計算量と比べて大きくは増大しない. 行時間に大きく影響する．したがって，提案する分割戦略. ことが示されている．このため，動的計画法の実行オーバ. c 2019 Information Processing Society of Japan ⃝. 6.
(8) Vol.2019-HPC-169 No.3 2019/5/10. 情報処理学会研究報告 IPSJ SIG Technical Report. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 図 6 計算量を最小とする分割点（n = 4000, k = 3, p = 0.02） ．二分木の節の数値（黒字）は 行列の次数を示し，節の下の数値（赤字）はその分割における r の値を示す．. を適用した場合に，デフレーションが計算量や実行時間に. [11]. どの程度の影響を与えるか評価が必要である． 謝辞. 本研究の一部は東京電機大学総合研究所研究. Q19T-09 として行った． [12]. 参考文献 [1]. [2]. [3]. [4]. [5]. [6]. [7]. [8]. [9]. [10]. Golub, G. H. and Van Loan, C. F.: Matrix Computations Fourth Edition, Johns Hopkins University Press (2013). Bischof, C. H., Lang, B. and Sun, X.: A Framework for Symmetric Band Reduction, ACM Transactions on Mathematical Software (TOMS), Vol. 26, No. 4, pp. 581–601 (2000). Martin, R. S., Reinsch, C. and Wilkinson, J. H.: The QR Algorithm for Band Symmetric Matrices, Numerische Mathematik, Vol. 16, No. 2, pp. 85–92 (1970). Arbenz, P.: Divide and Conquer Algorithms for the Bandsymmetric Eigenvalue Problem, Parallel Computing, Vol. 18, No. 10, pp. 1105–1128 (1992). Gansterer, W. N., Schneid, J. and Ueberhuber, C. W.: A Divide-and-Conquer Method for Symmetric Banded Eigenproblems-Part I: Theoretical Results, Technical report, AURORA TR1999-12, Vienna University of Technology (1999). Ishigami, H., Hasegawa, H., Kimura, K. and Nakamura, Y.: A Parallel Bisection and Inverse Iteration Solver for a Subset of Eigenpairs of Symmetric Band Matrices, Proceedings of International Workshop on Eigenvalue Problems: Algorithms, Software and Applications in Petascale Computing, Springer, pp. 31–50 (2017). Cuppen, J.: A Divide and Conquer Method for the Symmetric Tridiagonal Eigenproblem, Numerische Mathematik, Vol. 36, No. 2, pp. 177–195 (1980). Dongarra, J. J. and Sorensen, D. C.: A Fully Parallel Algorithm for the Symmetric Eigenvalue Problem, SIAM Journal on Scientific and Statistical Computing, Vol. 8, No. 2, pp. s139–s154 (1987). Gu, M. and Eisenstat, S. C.: A Stable and Efficient Algorithm for the Rank-one Modification of the Symmetric Eigenproblem, SIAM Journal on Matrix Analysis and Applications, Vol. 15, No. 4, pp. 1266–1276 (1994). 廣田悠輔，今村俊幸： 帯行列の一般化固有値問題向け分 割統治法，情報処理学会論文誌コンピューティングシス テム (ACS)， Vol. 8, No. 4, pp. 78–87 (2015).. c 2019 Information Processing Society of Japan ⃝. [13]. [14]. [15]. Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A. and Sorensen, D.: LAPACK Users’ Guide, SIAM, Philadelphia, PA, third edition (1999). Intel Math Kernel Library (online): https://software. intel.com/en-us/mkl (2019.04.09). Bischof, C. H., Lang, B. and Sun, X.: Algorithm 807: The SBR Toolbox — Software for Successive Band Reduction, ACM Transactions on Mathematical Software (TOMS), Vol. 26, No. 4, pp. 602–616 (2000). Fukaya, T., Yamamoto, Y. and Zhang, S.-L.: A Dynamic Programming Approach to Optimizing the Blocking Strategy for the Householder QR Decomposition, Proceedings of 2008 IEEE International Conference on Cluster Computing, IEEE, pp. 402–410 (2008). 深谷猛，山本有作， 張紹良： 動的計画法を用いたブ ロックハウスホルダ QR 分解アルゴリズムの性能最適化， 情報処理学会論文誌コンピューティングシステム（ACS） ， Vol. 4, No. 4, pp. 146–157 (2011).. 7.
(9)
図
関連したドキュメント
課題名（英文） Study on Optimal Dividing Strategy in the Divide-and-Conquer Algorithm for Banded Eigenvalue Problems 研究代表者
Amari, Dualistic Differential Geometry of Positive Definite Matrices and Its Applications to Related Problems, Linear Algebra and its Applications, Vol.247, 31-53 (1996). Eguchi,
In a multiplicity analysis of a symmetric eigenvalue problem, an exact characteristic polynomial is obtained by transforming symmetric matrix to Frobenius form in
For a real symmetric definite generalized eigenproblem A v = λ B v of large size, the filter diagonalization method is used to solve approximations of those eigenpairs
By the filter diagonalization method whose filter is a linear combination of resolvents, some results of experiments are shown to solve only those pairs of a symmetric
Experiments of filter diagonalization method for real symmetric definite generalized eigenproblems by the use of elliptic filters Hiroshi Murakami†1 For a real
Keywords: generalized eigenvalue problem, tridiagonal matrix, banded matrix, divide and conquer method, multicore.. 計算機）では，CPU
Abstract: In previous researches, we have shown that for the generalized eigenproblem Av = λBv whose coefficient matrices both of A and B are real symmetric and B is also
