検索対象:     
報告書番号:
※ 半角英数字
 年 ~ 
 年

Condition number estimation of preconditioned matrices

前処理済み行列の条件数推定

櫛田 慶幸

Kushida, Noriyuki

本論文では前処理済み行列の条件数を推定する新しい手法を開発した。これにより、現在主流の線形連立一次方程式解法であるクリロフ部分空間法の収束性を向上させ、シミュレーションの時間を短縮することが可能となる。従来、前処理済み行列の条件数を推定するためには、(1)密行列になることを受け入れ実際に前処理行列を作用させるか、(2)ランチョスコネクションと呼ばれるランチョス法に基づき固有値を推定する方法が用いられてきた。しかしながら、(1)はメモリ使用量が膨大になるため実際のシミュレーションで使われる規模の行列では事実上不可能であり、(2)は本論文で示すように計算誤差のため実用には程遠い。このため、本論文ではある行列の逆行列の行列ノルムを推定するHagerの方法に基づき、前処理済み行列の条件数を推定するアルゴリズムを開発した。Matrix Marketから得らるサンプル行列や、ポワソン方程式をFEMで離散化した行列を用いて精度検証を行ったところ、ランチョスコネクションが意味のない推定値をだす条件であっても、新手法は安定していることが示された。また、計算量およびメモリ使用量の解析を行い、計算量は実際のシミュレーションに必要な量の4倍が必要となるが、メモリ使用量についてはほぼ同量しか必要とならないことが示された。これにより、開発した新手法が従来手法(1),(2)の問題点を克服したと言える。

The present paper introduces a condition number estimation method for preconditioned matrices. The newly developed method provides reasonable results, while the conventional method which is based on the Lanczos connection gives meaningless results. The Lanczos connection based method provides the condition numbers of coefficient matrices of systems of linear equations with information obtained through the preconditioned conjugate gradient method. Estimating the condition number of preconditioned matrices is sometimes important when describing the effectiveness of new preconditionerers or selecting adequate preconditioners. Operating a preconditioner on a coefficient matrix is the simplest method of estimation. However, this is not possible for large-scale computing, especially if computation is performed on distributed memory parallel computers. This is because, the preconditioned matrices become dense, even if the original matrices are sparse. Although the Lanczos connection method can be used to calculate the condition number of preconditioned matrices, it is not considered to be applicable to large-scale problems because of its weakness with respect to numerical errors. Therefore, we have developed a robust and parallelizable method based on Hager's method. The feasibility studies are curried out for the diagonal scaling preconditioner and the SSOR preconditioner with a diagonal matrix, a tri-daigonal matrix and Pei's matrix. As a result, the Lanczos connection method contains around 10% error in the results even with a simple problem. On the other hand, the new method contains negligible errors. In addition, the newly developed method returns reasonable solutions when the Lanczos connection method fails with Pei's matrix, and matrices generated with the finite element method.

Access

:

- Accesses

InCites™

:

パーセンタイル:45.34

分野:Multidisciplinary Sciences

Altmetrics

:

[CLARIVATE ANALYTICS], [WEB OF SCIENCE], [HIGHLY CITED PAPER & CUP LOGO] and [HOT PAPER & FIRE LOGO] are trademarks of Clarivate Analytics, and/or its affiliated company or companies, and used herein by permission and/or license.