大規模線形方程式ソルバーを高速化する前処理手法の開発とその応用

点击翻译按钮获取中文摘要

本年度は,線形方程式Ax=bを高速に解くための前処理,および前処理行列の対称正定値行性を保存するような前処理付きアルゴリズムについて研究をすすめた.まず,従来はKrylov空間法のアルゴリズム(外部反復)の反復の過程でK^<-1>ν(Kは前処理行列)を求めることによって前処理を行うのに対して,われわれはA^<-1>νの近似を求めることによって前処理する方法を提案した.ここで,A^<-1>νの近似はAz=νをある精度まで反復法で解くこと(内部反復)によって求められる.そして,この提案する前処理の概念を一般化共役残差法に実装し,その収束性を解析した.また,内部反復に定常反復法(逐次過剰緩和法など)を用い,定常反復法とKrylov空間法との融合を実現した.数値実験では,従来の前処理では解けない問題や多くの計算時間を要する問題に対して顕著な効果があった.特異な系に残差最小化アプローチに基づく解法を適用すると,理論的には残差ノルムは最小残差に収束することが知られている.しかしながら,実際の計算では,最小残差に収束した後にそれ以下の値になる(理論と矛盾).そこで,われわれは以前に,理論が示すと通りに収束する改良版アルゴリズムを提案した.その解法に前処理を施したアルゴリズムを考える場合,計算量を増やすことなく係数行列の対称正定値性を保存することはできない.そこで,計算量を増やすことなく,かつ係数行列の対称正定値性を保存する前処理付きアルゴリズムを提案した.数値実験では,対称正定値性を保存するアルゴリズムが対称正定値性を保存しない場合よりも有効であることを示した.