AP1000を用いた下三角疎行列の直接解法

概要

論文の詳細を見る
下三角疎行列Lを係数とする方程式L_x=bを,複数個の右辺bについて解く必要がある場合に,Lの逆行列を利用する並列解法が知られている(Alvarado et al.,川北[5]参照).この解法では,下三角疎行列Lを次のように分解する.L=L_1L_2・・・L_n (1)ただし(L_k)_<il>=L_<ik> for k≤i≤n(_k)_jj≡1 for j≠k(L_k)≡O otherwiseである.ここでL_kをいくかのグループに分けて,行列Lを次のように表すことができる.L=Π^^m__<k=m>P^<-1>_kb (2)このとき,各P_kの逆行列P^<-1>_kを計算しておけば,複数の右辺bについて,x=L^<-1>b=Π^^1__<k=m>P^<-1>_kb (3)と解くことができる.Lの逆行列L^<-1>は,一般に下三角疎行列Lよりも非ゼロ要素が多くなってしまうが,各P_kに対し,その逆行列P^<-1>_kが新たな非ゼロ要素を生成しないようなグループ分けを考えることにより,行列Lの疎という性質を生かすことができる.また,L^<-1>をこのように分解することにより,並列計算機においては,P^<-1>_kの計算に必要なすべての乗算を同時に行なうことができるので,並列計算機において高速に処理することができる.この解法では,グラフの概念をとり入れた前処理により,行列Lの分解(2)を決定するが,複数の右辺bを想定しているので,分解アルゴリズムよりも,式(3)の計算を高速に行なうことが重要となる.実際の式(3)の計算では,行列P^<-1>_kの各非ゼロ要素にたいして1回ずつ乗算をおこなうので,並列計算機のセルの個数が,各P^<-1>_kの非ゼロ要素数を上回っていれば,全非ゼロ要素を別々のセルに配置して,P^<-1>_kbの乗算をワンステップですますことができる.この場合,式(3)の全対の計算量は,グループ数mに依存する.したがって,セル数などの制約がなければ,グループ数を減らすことが有効である.
1995-03-15

AP1000を用いた下三角疎行列の直接解法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク