早期リスタートによるGMRES（m）法の高速化

情報処理学会 Web Site 被引用文献8件 参考文献11件

書誌事項

タイトル別名
  • ソウキ リスタート ニ ヨル GMRES m ホウ ノ コウソクカ
  • The Speedup of the GMRES (m) Method Using the Early Restarting Procedure
  • 数値計算

この論文をさがす

抄録

偏微分方程式の境界値問題を有限差分法や有限要素法を用いて離散化すると 大規模かつ疎で正則な係数行列を持つ連立1次方程式が生じる.これらの連立1次方程式は一般に反復法を用いて解くことが多い.本稿ではKrylov部分空間法の1つであるGMRES法について考える.GMRES法は各反復で残差ノルムを最小にする算法である.しかし 必要とする計算時間と記憶容量が反復回数とともに増加してしまうため 通常はりスタート型のGMRES(m)法が使われる.このGMRES(m)法に対してリスタート周期mの適切な設定が問題となる.リスタート周期を短く設定すると 収束するまでの反復回数が膨大になったり もしくはまったく収束しないという可能性が高くなる.逆に リスタート周期を必要以上に長く設定すると 計算時間が膨大になる.本稿ではりスタート周期を自動的に早める手法を提案する.この手法はりスタート周期を早めることで不必要な計算を行わないようにし 計算時間を短縮することである.いくつかの数値実験の結果から 本稿で提案する手法は 問題の規模が大きいほどオーバヘッドの比率を小さくし 計算時間を短縮する効果を発揮する算法であることを示す.

Using a finite difference method or a finite element method to discretize an elliptic boundary value problem of partial differential equation, we obtain systems of linear algebraic equations,where the coefficient matrix is large, sparse, and nonsingular. These systems are often solved by using iterative methods. In this paper, we focussed on the GMRES method, one of the mostwidely utilized Krylov subspace methods. The GMRES method minimizes residual norms ateach iteration step. The major drawback to the GMRES method is that the amount of workand storage required per iteration increases linearly with the iteration count. As a result, the GMRES(m) method, the restarted version of the GMRES method, is used. The difficultylies in choosing the appropriate restarting frequency m. If m is too small, the GMRES(m)method may be slow to converge, or may fail to converge entirely. A value of m that islarger than necessary involves excessive work. We developed a procedure that automaticallyconducts the early restarting. The effect of the early restarting is to decrease excessive work.The new method is shown to have good numerical properties for large scale problems.

収録刊行物

被引用文献 (8)*注記

もっと見る

参考文献 (11)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ