定常反復法とクリロフ部分空間法の共演-線形計算の新しい展開を目指して-

稳态迭代法与Krylov子空间法的结合 - 瞄准线性计算新发展 -

基本信息

批准号：
16656034
负责人：
杉原正顯
金额：
$ 1.92万
依托单位：
The University of Tokyo (2005)Nagoya University (2004)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Exploratory Research
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2005
项目状态：
已结题

项目摘要

本研究の目的は,現在の線形計算アルゴリズムの主流であるクリロフ部分空間法(共役勾配法等)に,収束が遅いため,昨今顧みられることのなかった定常反復法(SOR法等)を組み込んで,より高速な線形計算アルゴリズムを開発することである.本年度も昨年度に引き続いて,連立1次方程式の数値解法にかぎり,研究を進めた.具体的には,クリロフ部分空間法(ペトロフ・ガレルキン方式に基づく解法系(Bi-CG法,CGS法,Bi-CGstab法,Bi-CGstab2法,GPBi-CG法,GPBi-CG(ω)法),最小残差方式に基づく解法系(GMRES(k)法,GCR(k)法,QMR法))に,前年度は用いなかったADIによる前処理を組み入れた.しかし,ADI法はパラメータ設定が難しく,収束が非常に速くなる場合もあるが,逆もあり,頑健性に欠けるという結果となった.前年度の結果も踏まえると,実装の簡便さ,およびその頑健性からすると,反復回数一定のSOR法を前処理に用いるのが最も有効であるという結論となる.本年度は,基盤になるクリロフ部分空間法に関する研究も進めた.具体的には,対称行列用解法の共役残差法を非対称行列用に拡張した。従来は,共役残差法を,最小残差方式に基づく解法系と位置づけ,非対称行列用に拡張し,GCR法などが得られていた.本研究では,共役残差法を,ペトロフ・ガレルキン方式に基づく解法系として位置づけ,その非対称版(Bi-CR法と名づけた)を得ることに成功した.さらに,数値実験を通じてではあるが,ペトロフ・ガレルキン方式に基づく解法系の大本に当たるBi-CG法よりも良い収束性を示すことも確認した.

本研究的目的是将最近由于收敛速度慢而没有被考虑的平稳迭代方法（SOR方法等）融入到目前主流的Krylov子空间方法（共轭梯度方法等）中。目前的线性计算算法，目标是开发更快的线性计算算法。继去年之后，今年我们将继续因此，研究仅限于联立线性方程组的数值解。具体来说，Krylov子空间法（基于Petrov-Galerkin法的解体系（Bi-CG法、CGS法、Bi-CGstab法、Bi-CGstab2法、GPBi法） -CG法、GPBi-CG(ω)法)、最小残差法我们将前一年没有使用过的ADI预处理融入到基于该方法的求解系统中（GMRES(k)方法、GCR(k)方法、QMR方法）。但是，ADI方法很难设置参数。并且收敛性非常低，在某些情况下速度更快，但在其他情况下结果不太稳健。前一年的结果也是如此。基于此，得出的结论是，从易于实现性和鲁棒性来看，迭代次数恒定的SOR方法对于预处理来说是最有效的。今年，我们还将对Krylov子空间方法进行研究，它是具体来说，我们扩展了共轭残差法（对称矩阵的解决方案）以用于非对称矩阵。传统上，共轭残差法被定位为基于最小残差法的解系，并被推广到用于非对称矩阵以获得GCR方法。在本研究中，共轭残差法被定位为解系系统基于我们成功地获得了一个非对称版本（称为Bi-CR方法）。尽管通过数值实验，我们表明它比Bi-CG方法具有更好的收敛性，而Bi-CG方法是基于Petrov-Galerkin方法的主要求解系统。我也证实了这一点。