一般固有値問題における前処理付共役勾配法による大次元スパース対称行列の固有解の一算定法

概要

論文の詳細を見る
1 はじめにコンピュータの計算速度,容量など,その性能は指数関数的に進歩して現在に至っており,計算力学などによる数値シミュレーションは実用化の時代に入ったといえる.そして,それぞれの分野の解析法は,大次元の連立1次方程式あるいは固有値問題に帰着する.現在,ソルバーとしてICCG法,SCG法等の前処理を施した共役勾配法系の反復法(PCG法)やAMG法とCG法を組み合わせた方法などが並列化と共に注目されている.これらは,消去法に比べ主記憶領域を極めて少なくできるため,有限要素法などに見られる大次元でスパースな行列に対して有力な解析手段となる.提案法はICCG法やSCG法などの前処理を施した共役勾配法系の反復法や原点移動逆べキ乗法および2分法を利用しながら,大次元スパース行列で小さい方からあるいは大きい方から数個の固有解を求める場合に有効である.大きい方から数個の固有解を求める場合も,逆ベキ乗法で小さい方から数個の固有解を求める場合と同様に数値解析できるのが特徴である.逆ベキ乗法やサブスペース法は要求される固有解以外の解を求める必要があるが,提案法はその必要がないので,計算機の記憶容量を最小限に押さえられると共に,正定値性と非正定値性を利用した方法の採用および固有解以外の解を求める必要がないことにより,計算時間の大幅な短縮化も可能としている.多重根に対しては収束が遅いのが一般的であるが,提案法は逆に早くなる特徴も持っている.また,固有解は小さい方からあるいは大きい方から順番に確実に求められるので安定性を保持した解法ともなっている.2 共役勾配法による固有解一般固有値問題は[A^^~-λB^^~]φ=0によって与えられる.ここに,A^^~はn×nの実対称行列で,B^^~はn×nの正値実対称行列であり,λは固有値で,φは対応する固有ベクトルである.シルベスター慣性則を応用したPCG 法により行列Aの符号数が決定される.しかし,数値計算で生じる丸め誤差のために,極小次元問題の場合を除いて,共役方向ベクトルに関する行列Aの共役性が演算の進行に伴いくずれていく.そのために,提案法によって計算された試行固有値が正しい固有値に接近するとき,符号変化数が正しく求まらない.この不安定性を避ける方法を提案した.最小固有解からいくつかの固有解を求める場合と最大固有解からいくつかの固有解を求める場合について@の考え方を示した.3 アルゴリズム提案法のアルゴリズムの1例を本文に示した.4 数値実験提案法の検証のために,本法と2分法を使い,近似固有解を求めた後,原点移動逆ベキ乗法と2分法を使って,固有解の精度を向上させる手順により,標準固有値問題および一般固有値問題に対する数値実験を行った.また,提案法との比較のために,サブスペース法を使用した.最初に,長方形領域における2次元ヘルムホルツ方程式を離散化して生じる標準固有値問題を扱う.Figs.3-6は2分法におけるステップ毎のICCG法の反復回数と試行固有値の収束状況を表している.小さい方から5個の固有解を求める場合,非正定値行列の時,試行固有値が実際の固有値に近づくまでは,ICCG法の反復回数は1回(ステップ1から5)と極端に少なく,急激に固有値の存在範囲は狭まっている.解に近づいても10回以内と非常に少ない.正定値行列の時,収束判定値を満足するまでICCG法は反復を行っている.Fig.5から,提案法は,2分法を利用することによりleft(左試行固有値)とright(右試行固有値)が次第に狭まり,確実に固有値に収束している.また,Figs.4と6から,大きい方から5個の固有解を求める場合も,小さい方から5個の固有解を求める場合と同様な傾向を示した.Figs.7-8はサブスペース法とのCPU時間の比較を描いているが,小さい方から5個の固有解を求める場合,サブスペース法のおよそ1/39〜1/60(<40000自由度)の時間で,また,大きい方から5個の固有解を求める場合,サブスペース法のおよそ1/23〜1/124(<40000自由度)の時間で計算されており,自由度の増加に伴いその差は指数関数的に大きくなる傾向を示した.2番目の計算例は,Fig.9に示すように剛節節点を有する建築骨組についての有限要素法(FEM)による一般固有値問題である.ここでは,工学系で必要とされる小さい方から5個の固有解を提案法とサブスペース法の両方法によって計算した.数値実験に用いたパラメーターをTable3に示す. 表に示されるように,5通りの自由度に対して数値計算を行った.固有値の探索は最初の計算例と同様な性状を示しており,ここではその説明を省いた.Figs.10-11はサブスペース法とのCPU 時間の比較を描いているが,サブスペース法のおよそ1/5-1/22の時間で計算されており,最初の計算例と同様に自由度の増加に伴いその差は大きくなることを示した.FEMにおいても,同様な傾向を示すものと思われる.5 結語理論的には,sign(p^TAp)によって対象とする行列の符号数を計算できるので,PCG法の計算をしながら固有値の個数をカウントできる.演算時の誤差の影響を受けなければ,ハウスホルダー2分法のように固有解を求め得る方法であるが,丸め誤差により固有解の近傍では符号変化数を正しくカウントできない場合がほとんどである.その対処法として,行列の2次形式の固有ベクトルによる表現式および行列の正定値性と非正定値性を利用して確実かつ迅速に固有解を求める方法を提案した.多重根を持つ行列に対して収束は遅くなるのが一般的であるが,提案法の理論と数値実験により,特に多重根を持つ行列の方がそうでない行列より早く収束することが示された.本法はPCG法系の解法であるので,大次元スパース行列で小さい方あるいは大きい方から数個の固有解を必要とする場合に有効であり,要求される固有解以外の解を必要としないので,計算機の記憶容量を最小限に押さえられる,計算時間も短い,精度も良い,安定性のある解法と考えられる.また,並列用PCG法を用いれば並列処理による高速化も可能である.
2008-07-30

著者

柏木光博
東海大学産業工学部

一般固有値問題における前処理付共役勾配法による大次元スパース対称行列の固有解の一算定法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク