No | 216610 | |
著者(漢字) | 曽我部,知広 | |
著者(英字) | ||
著者(カナ) | ソガベ,トモヒロ | |
標題(和) | 共役残差法の拡張 | |
標題(洋) | Extensions of the Conjugate Residual Method | |
報告番号 | 216610 | |
報告番号 | 乙16610 | |
学位授与日 | 2006.09.14 | |
学位種別 | 論文博士 | |
学位種類 | 博士(工学) | |
学位記番号 | 第16610号 | |
研究科 | 工学系研究科 | |
専攻 | 物理工学専攻 | |
論文審査委員 | ||
内容要旨 | 計算機を用いて多自由度系の現象を解明する科学技術計算の方法は,理論や実験と同様に科学的方法の一つとして広く認知されており,近年の計算機の発達によりその重要性が益々高まっている.このなかで,科学技術計算の基盤を支える高品質な数値計算アルゴリズムを開発することは必要不可欠であり,特に応用諸分野で頻繁に現れる大規模連立一次方程式に対する高速・高安定数値解法の開発は重要な課題である. 連立一次方程式の数値解法は,直接法,定常反復法,そしてクリロフ部分空間法に大別される.直接法のなかでLU分解法は代表的であり,中小規模の問題に対して有効である.しかしながら,所要演算量が行列サイズの3乗に比例するため,大規模行列に対する計算時間の爆発的増加が問題となる.定常反復法の代表としては逐次過剰緩和(SOR)法があり,実装の容易さのため特に流体計算分野で普及しているが,特定のクラスの行列しか適用できないため近年の多様化する問題に対応しきれないのが現状である.一方,クリロフ部分空間法は近年急速に発展を遂げた解法であり,共役勾配(CG)法と共役残差(CR)法が代表的である,そして,これらはエルミート行列用であるため,特にCG法の非エルミート行列用への拡張である双共役勾配(Bi-CG)法が1976年に提案されて以降,Bi-CG法の積型解法とよばれる加速手法の開発が自乗共役勾配(CGS)法を発端として現在国際的に主流な研究テーマの一つである. 本論文では,主流であるBi-CG法の加速手法の開発を行うのではなく,その基幹解法であるBi-CG法よりも高性能な基幹解法を探すべく,CR法を非エルミート行列用や複素対称行列用に拡張した.そして,得られたアルゴリズムを基礎とする積型解法の理論がBi-CG法と同様に構築可能であることを示した.一方,Bi-CG法の積型解法の一つである自乗共役勾配(CGS)法に対して収束の安定化を図り,その方法は新たに提案された積型解法の一つに応用できることを示した.具体的な成果は以下の4点である. (A) CR法の非エルミート行列用への拡張:双共役残差(Bi-CR)法の提案 (B) CR法の複素対称行列用への拡張:共役直交-共役残差(COCR)法の提案 (C) Bi-CR法の積型解法の理論構築およびその一例である自乗共役残差(CRS)法の提案 (D) 自乗共役勾配(CGS)法の安定化 上記の項目(A)〜(D)がそれぞれ本論文の第3章〜第6章に対応しており,以下にそれらの詳細を述べる.まず,クリロフ部分空間法について説明する.クリロフ部分空間法とは,次の残差列 を生成する解法族の総称である.ここでWnはn次元部分空間であり,Kn(A,γ0)はn次元クリロフ部分空間とよばれ,以下のように定義される. (A)CR法は,式(1)において とし,x0を初期近似解としたアフィン空間x0+Kn(A,γ0)上で残差ベクトルの2-ノルムを短い漸化式で最小化する解法である.この結果,残差ノルムの単調減少性が保証され,数値実験においても安定な収束の振る舞いを示す.しかしながらAがエルミートでないならばこのような解法は短い漸化式,すなわち少ないメモリ量と演算量では一般には得られないことがFaber & Manteuffel (1984)によって示されている.そこで本研究ではCR法を非エルミート行列用に拡張するために,次の部分空間 を選択することにより短い漸化式を有する解法が得られることを示した.得られたアルゴリズムをBi-CR法と名付け,破綻が無ければ高々全空間の次元数の反復回数で収束することを示した.数値実験では多くの場合,Bi-CG法よりもその残差ノルムが滑らかであり,より速く収束したことからBi-CR法はBi-CG法と同様に重要な基幹解法となり得ることが分かった. (B) 複素対称行列を係数行列とする連立一次方程式は,音響学や大規模電子構造計算などの分野で頻繁に現れ,その高速解法の開発が強く望まれている.そこで本研究では,次の部分空間 を選択することにより短い漸化式を有する解法(COCR法)が得られることを示した.最小残差性は理論的に失われるものの,数値実験では,多くの場合ほぼ残差ノルムが単調減少し,定評のあるCOCG法と同程度以上の収束性を示したため,COCR法は実用性の高いアルゴリズムであることが分かった, 特に,係数行列Aが実対称のときにCOCR法はCR法に帰着するため,COCR法はCR法を複素対称行列用へ拡張した解法であるといえる,またBi-CR法は,係数行列Aが複素対称のとき,γ*(0)=γ0とすることにより式(3)は式(4)となるためCOCR法となり,エルミートのときはγ*(0)=γ0とすることにより式(3)は式(2)になるためCR法に帰着する.したがって,Bi-CR法は,CR法やCOCR法を非エルミート行列用へ拡張した解法であるといえる. (C) Bi-CR法の収束性を加速するために,Bi-CR法の積型解法の理論構築を行なった.具体的には,以下のように(A)で得られたBi-CR法の残差ベクトルに,原点で値が1となるn次多項式(加速多項式)を乗じた. 次に,Bi-CG法に対するこの種の加速法は十分に発達しているため,このアイディアをBi-CR法の積型解法に応用した.そして一例として,加速多項式をBi-CR法で用いられている多項式とすることにより自乗共役残差(CRS)法を導出し,数値例により自乗共役勾配(CGS)法よりも高速かつ高精度の近似解を生成することを検証した.またCRS法は,Helmholtz方程式の境界値問題で他の有力なBi-CG法の積型解法であるBi-CGSTAB法やGPBi-CG法よりも高速かつ高精度の解を生成したため,非エルミート行列を係数行列に持つ連立一次方程式の有効な解法になることが分かった. (D) Bi-CG法の積型解法の一つであるCGS法は,他の有力な積型解法よりも速く収束することがあるがその収束の不安定さが問題とされている.そこで,まずCGS法で用いられている多項式を包含する新しい多項式を用いて残差ベクトルを再定義した,次に,その多項式に含まれている一つの自由パラメータを残差ノルムの局所的最小化に用いることによりCGS法の加速・安定化を図り,その有効性を数値実験で検証した.また,このアイディアは上述のCRS法にも応用可能であることを示した. 以上のように,本論文ではCR法を非エルミート行列用や複素対称行列用に拡張し,得られたアルゴリズムの性質に関する理論的な解析を行なった,そして,数値実験によりそれらの性能評価を行なった.更にBi-CR法を基礎とした積型解法の理論を構築し,例としてCRS法を導出し,数値実験によりその有効性を検証した.一方,CGS法の収束性の向上に関する研究を行い,それがCRS法にも応用可能であることを示した. | |
審査要旨 | 物理学・工学的諸問題を計算機上で数値的に解明する際に、大規模で疎な連立一次方程式が頻繁に現れることから、この方程式を数値的に高速かつ高精度に解くことのできる解法の開発は重要な課題とされてきた。近年、その課題に答える解法としてクリロフ部分空間法が注目されており、その開発が現在国際的に主流な研究テーマの一つである。本論文は、 エルミート行列用のクリロフ部分空間法の一つである共役残差法を非エルミート行列用へ拡張するという基礎研究を行い、さらにそれを元にして新しく提案した複素対称行列用の解法および非エルミート行列用の積型解法は従来法よりも多くの場合おいて計算効率が良いことを数値実験により検証したものであって、全7章から成る。 第1章 "Introduction"では、科学技術計算の分野に現れる大規模で疎な連立一次方程式を効率良く解くことの重要性を説明し、その解法としてクリロフ部分空間法に焦点を当て、その従来研究の背景を紹介した上、本論文の目的・構成について述べている。 第2章 "Krylov subspace methods"では、本研究の基礎となるクリロフ部分空間法の枠組みを説明し、この視点からエルミート行列用、複素対称行列用、そして非エルミート行列用の解法を系統的に説明している。また、応用上重要である前処理について簡潔に述べている。 第3章 "Bi-CR: a biconjugate residual method"では、エルミート行列用の共役残差(CR)法の残差ベクトル列が満たすA-直交性をA-双直交性に拡張することにより、短い漸化式で共役残差法を非エルミート行列用に拡張することに成功し、その結果として、双共役残差(Bi-CR)法を提案した。そして、多くの数値例を通して、Bi-CR法は従来の重要な基幹解法とされてきた双共役勾配(Bi-CG)法よりも高速かつ良好な収束の振る舞いを示すことを検証した。この結果はBi-CR法を基礎とする新しい高速解法の開発の可能性を示唆しており、またその具体例を第4章および第5章で述べる。 第4章 "COCR: a conjugate orthogonal conjugate residual method"では、複素対称行列を係数とする連立一次方程式を高速に解く重要性を述べており、そのための解法である共役直交-共役残差(COCR)法を提案した。これは、複素対称行列に対してBi-CR法を適用して得られるアルゴリズムであるが、ここでは行列の特徴を利用してさらにその一反復当たりの演算量を半減させていることに成功した。そして、数値実験によりCOCR法は定評のあるCOCG法やQMR法と同等以上の性能であること示した。 第5章 "CRS: a conjugate residual squared method"では、非エルミート行列を係数とする連立一次方程式を高速に解くことを目的とし、Bi-CR法の残差ベクトルに対して行列多項式を乗じることにより収束の加速を図るという積型解法の導入を行った。その中から自乗共役残差(CRS)法を提案し、数値実験により従来法であるCGS法が収束する例において、CGS法、Bi-CGSTAB法、そしてGPBi-CG法などの著名な解法よりも多くの場合高速であり、得られる近似解も高精度であることを示した。しかしながら、CGS法が収束しない例ではCRS法の収束は遅くなることがあったため広く実用的であるとは言い難い。そこではBi-CR法の積型解法に用いる行列多項式の模索を今後の課題としている。 第6章 "SCGS: a stabilized CGS method"では、非エルミート行列用の高速解法であるCGS法は、しばしば不規則な収束の振る舞いを示すことに対して、その振る舞いを滑らかにする安定化自乗共役勾配法(SCGS)法を提案した。そして、数学的にSCGS法はCGS法よりも必ず少ない反復回数で収束することを証明しており、実際の数値例を通して、CGS法よりも良好な収束性を有することを検証した。最後に、SCGS法のアイディアを前章のCRS法に対して適用することにより、CRS法の更なる加速・安定化を図ることを今後の課題としている。 第7章 "Conclusion"は、前6章をまとめ、今後の課題および展望を述べたものである。 以上要するに、本論文は科学技術計算の分野に現れる大規模で疎な連立一次方程式の高速解法であるクリロフ部分空間法の枠組みの中から従来法よりも有用な基幹解法を提案した上、それを基礎とした実用的かつ高性能な解法を目的に応じて開発したものであって、理論と応用の両方にとって重要な結果であり、物理学・工学的諸問題の計算機上での数値的な解明に資すると期待される。これらの点で、本研究は数理工学の発展に寄与するところが大きい。よって本論文は博士(工学)の学位請求論文として合格と認められる。 | |
UTokyo Repositoryリンク |