大規模非対称固有値問題の数値解法は近年研究の活発な分野の一つであるが,従来は十分な研究がなされているとは言えなかった.QR法は問題サイズnに対して(n³)の計算量を要し,制限が大きい.またArnoldi法,two-sided Lanczos法,Davidson法などの手法については,十分にその性質が解明されていなかった.過去数年間にこの分野では大きな発展が見られ,反復毎に必要な記憶容量が増大するArnoldi法は,リスタート付反復解法の提案によって最も実際的な解法となっている.リスタート付Arnoldi法は効率的な解法であるが,必要な固有値が密集している場合には部分空間の次元が大きくなりやすい.本研究では収束を加速することによってこの問題点を改善できることを示し,数値実験によりこの加速法の特性を明らかにした.さらに,Arnoldi法の計算量の大部分を占めるQR法部分の効率的な並列計算に関する研究を行ない,分散メモリ型並列計算機AP1000+上にこれを実装してその効果を検証した.

　非対称行列A∈R^n×nの優越固有解(_i,u_i),1irを求めることを考える.これは次元m≪nのベクトル部分空間K上への直交射影によって近似でき,射影行列を用いてを満たす∈C,∈Kを計算すればよい.Arnoldi法は、適当なr次元部分空間Sによって生成されるKrylov部分空間K_l＝span(S,AS,…,A^l-1S),l＝1,2,…,m(・)とすれば任意の初期ベクトルx₁∈Cⁿに関して(A)x₁＝u₁(₁)₁+…+u_n(_n)_nと展開できるので,固有解(u_i,_i)が必要なr個から順に並べられているとすれば,条件max_{i＝r+1,…,n}|(_i)|i＝1,…,r|(_i)|を満たすように多項式を選べばよい.多項式加速法による計算例を図1に示す.

図1.Convergence of the restarted Arnoldi iterations(m＝10)for the rightmost eigenvalue of test problem CHEMWEST(1501),with computed spectra of the problem

　このうちChebyshev多項式による加速法は,領域∋_r+1,_…,_nにおける最大絶対値を最小とする多項式がChebyshev関数として表現できることを利用した手法であるが,非対称固有値問題においてはが楕円領域となるため,最適な領域の決定が難しい.実際,従来のアルゴリズムでは必要な固有値が領域内部に含まれる場合や,不要な固有値の一部が外部に残される場合があり,このようなケースでは収束が極端に遅くなることが数値的に証明できる.

　これに対して本研究では近似固有値から構成される凸包領域を用いたアルゴリズムを提案し,この問題点を解消することに成功した.まず固有値_r+1,_…,_nから凸包を生成し,その境界上で適当な重み関数を用いてL₂ノルムを定義する.ここでは計算の安定性の観点からChebyshev関数を用いた.最大値の原理から,領域内の複素関数はその最大値を領域境界上で取る.したがって問題は境界上で定義されるノルムを最小化する多項式の計算に帰着される.一般に,あるノルムに関して定義される直交系は同次の多項式に対して極小性を持つ.すなわち凸包境界上でChebyshev重みに属する直交系を生成してやれば,これらは加速多項式としての条件を満たす.以上の考察により,凸包領域に関する加速多項式が容易に計算できることが分かる.

　Arnoldi法の計算は以下のように行なう.まず正規直交基底V₁＝[₁,_…,_r],基底の次元数m,多項式の次数kを決める.次にArnoldi法によりブロックHessenberg行列H_m∈R^mr×mrを求める.すなわちj＝1,_…,m-1について,W_j＝AV_jからH_i,j＝V^T_iW_j,W_j＝W_j-V_iH_i,j(i＝1,_…,j)を計算し,直交化Q_jR_j＝W_jによりV_j+1＝Q_j,H_j+1、j＝R_jを決める.H_mの固有解をQR法で計算し,近似固有値₁,_…,_r及び対応する近似固有ベクトル₁,_…,_rを求める.収束が十分でなければ不要な固有値から凸包を生成し,加速多項式_k()を定める.Z₀＝[₁,_…,_r]からを計算し,Z_kから得られる正規直交基底V₁を次の反復の初期ベクトル列とする.

　多項式の計算法は次のように行なう.最大値の原理により,加速多項式は近似固有値₁,_…,_rから生成される凸包の境界上で最大値を取る.凸包Hの頂点を,＝0,_…,とすれば,内積〈・,・〉_∂Hは

　で定義される.Chebyshev関数を用いて適当な関数列t₀,t₁,_…をで定義することにすれば,展開係数は3項漸化式_k+1t_k+1＝(-_k)t_k()-_kt_k-1()から容易に計算することができる.ノルムに関する正規直交基底₀,₁,_…はこれをもとに決定すればよい.

　行列のサイズをn,その非零要素の数をn_nz,ブロックArnoldiの反復回数をm,必要な固有値の個数をr、またChebyshev多項式の次数をkとすると,ブロックArnoldi法の計算量は(nm²r²)flopsであり,QR法によるmrのサイズの行列H_mの固有値の計算には(m³r³)flops,逆反復によるその固有ベクトルの計算には(m²r³)flopsの計算量がそれぞれ必要である.Chebyshev反復には,係数の計算には(k²)flopsを要するが,これらは前三者に比べれば無視できるほど小さい.

　さらにブロックArnoldi法を用いてHarwell-Boeingの疎行列コレクションから代表的な問題を選び,Chebyshev加速法との数値的な比較を行なった.問題のスペクトル分布との比較結果から,必要な固有値の絶対値が優越している場合には本研究によるアルゴリズムがより少ない反復回数で収束することが明らかになった.また,多項式加速を用いないアルゴリズムとの比較の結果からは,多項式加速がスペクトル分布に強く依存していることが分かった.スペクトルが密集していない場合には収束が遅くなるが,これは近似スペクトル分布が正確な場合と大きく異なっているためであると考えられる.また,部分空間反復法との比較結果からArnoldi法は非正規性の強い問題では重複固有値を落しやすいことが分かったが,これはArnoldi法の問題点の一つである.

　上述の計算量に関する結果は,Arnoldi反復内部で用いられるQR法を効率的に計算する必要性を示している.そこで本研究では,QR法の効率的な並列計算に関する研究を行ない,分散メモリ型並列計算機AP1000+上に実装してその効果を実証した.

　大部分の固有値解法はQR法を内部で実行しているが,QR法部分には(n)の並列性しかないため,この計算がボトルネックとなる.このため非対称固有値解法の並列化に関する従来の研究では,いずれも低い並列性しか得られていなかった.Arnoldi法の並列化に関しても共有メモリ型並列計算機を用いた研究や並列線形計算ライブラリなどを用いた研究が行なわれているが,この問題については解決されていない.QR法の収束は部分空間の次元数mが大きくなるほど速くなるが,flop数は逆に大きくなる.したがってArnoldi法においてQR法がボトルネックになることを避けるためには,mはできるだけ小さく取らなければならなかった.

　QR法には以上のような問題点があるが,これはデータ分割を工夫することでかなり改善することができる.QR法の並列化効率は行列の次元nとプロセッサ数pに対して,n/pでほぼ決まる.一定の並列化効率を維持するためにn/p＝rを固定すると,1プロセッサあたりの記憶容量はrnとなるが,並列化効率が低ければrは大きくなるため,nに対して必要な記憶容量が確保できなくなる.したがって並列化に際しては効率を特徴付けるr＝n/pを小さく抑えることが重要となる.本研究では,計算効率の改善のためにデータマッピングを改良し,完全なロードバランスを実現すると同時に,通信レイテンシを完全に隠蔽するパイプライニングを可能とした.またAP1000+の高速通信手法を利用してオーバーヘッドを最小限に抑えた.この結果これまでの他の研究に比べてはるかに高い並列化効率を実現し,並列化効率50%を与えるrは従来のおよそ1/4の40となった.

　本研究で得られた成果は以下の通りである.まずArnoldi法の効率的な加速法を提案し,加速多項式の簡単な決定法を示した.さらに代表的な問題を用いた評価により,ある種の問題については従来の解法に比べて非常に少ない計算量で解が得られることを示した.ただし本手法の収束率がスペクトル分布に強く依存することも明らかとなった.また並列化に関しては,QR法部分がボトルネックとなるものの,かなりの性能向上が実現できることを示した.ただし計算量の問題を回避するためには,Hessenberg行列の次元はできるだけ小さく取らなければならず,精度上の問題が生じる.この点についての研究は今後の課題である.

　大規模非対称固有値問題の数値解法は,数値解析学において複雑かつ豊富な内容を持つ研究分野の一つであるが,特に近年Saad,Sorensen,van der Vorstらによって精力的に研究が行なわれ,効率的な反復法の端緒が開かれた。すなわち,射影法における反復の過程で,近似固有値の分布を基に収束を加速する多項式を構成し,これをRitzベクトル列に適用することによって収束を加速できることが示されたのである.しかしこのための最適な多項式の決定は難しく,従来用いられた手法は複雑かつ柔軟性に欠けるものであった.

　著者は直交多項式の特性を巧妙に用いることによってこの問題を解決し,さらにこの解決の諸性質を詳細に調べて,その成果を主論文及び関連諸論文に発表したものである.

　主論文では,著者は主として加速多項式の最適性及びその実装について考察を行なっている.以下にその主要な結果を述べる.

　1.最適な加速は一般にはChebyshev多項式により実現できるが,この場合非対称問題においては減衰の対象となる領域が楕円形状を取るため,問題の固有値分布の形状によっては収束の効果が十分得られなかった.そこで本論文では,最大値の原理を用いて、減衰させるべき領域における最大最小問題をその境界上での問題に帰着し,境界上でL₂ノルムを定義した上で,このノルムの最大値を最小化する多項式を決定する方針が取られている.著者はこのような関数空間においてもBesselの不等式が成り立つことを用いて,この空間で構成される正規直交多項式系が最適多項式としての性質を満たすことを示し,さらにその具体的な決定法を与えている.この結果,加速過程が著しく簡素化されることが明らかとなった.

　2.以上の考察から導出されたアルゴリズムについて,その特性,特に固有値分布と収束性との関連が一連の数値計算により詳細に調べられている.これにより,本手法の有効性が十分に確認された.

　3.計算量の評価結果から,Ritz値の計算で用いられるQR法が効率化の障害となっていることを示した上で.著者はこれを並列計算と関連付け,実際に効率的な計算が実現できることを並列計算機上で数値的に実証した.

　以上のように,著者は多項式加速を簡素化する新たな提案を行なうと共に,実装及び評価についても詳細かつ良好な結果を与えており,著者の厳密な手法は評価することができる.また本研究は海外においても高く評価されており,この分野における貢献も少なからぬものと考える.審査担当者は,以上の理由により,本論文が博士(理学)の学位論文として充分な内容を持つものであると一致して判定した.なお,本論文第7章の一部は須田礼仁氏,小柳義夫氏との共同研究であるが,論文提出者が主体となって提案,評価を行なったもので,論文提出者の寄与が充分であると判断する.

　以上により論文提出者西田晃は博士(理学)の学位を授与される資格が十分にあるものと認める。