櫻井 隆雄
2014/10/22 (水), 15:00-17:00
東京大学 工学部6号館 235号室
大規模な疎行列を係数とした疎行列反復解法の収束性を向上させるための前処理法が提案されており[1]，その中でも不完全LU分解前処理は悪条件の行列に有効となると言われている．不完全LU分解前処理は，行列AをLU分解する際に，分解された上三角行列Uと下三角行列Lの非零要素の一部を零とすることにより計算コストとメモリ使用量を削減している．特に，非零要素の値の大きさや1行あたりの個数で制限する方式は閾値付不完全LU分解(ILUT)前処理と呼ばれている[2]．
ILUT前処理の改良方式は様々なものが提案されているが，今回の輪講では，次にあげる2論文を紹介する．1つ目の論文は非零要素をその値の大きさではなく，除去した際に生じる|A-LU|の大きさにより制限する方式[3]，2つ目は1行あたりの非零要素の個数を一定値にせず，分解後の行のノルムの大きさにより非零要素の個数を増減させる方式[4]を提案している．これらの方式の詳細と，収束性の向上効果を数値実験により評価した結果を述べる．
参考文献
[1] Y. Saad, Iterative methods for sparse linear systems., SIAM (1996).
[2] Y. Saad, ILUT: A dual threshold incomplete LU factorization., Numerical Linear Algebra with Applications, pp.387-402 (1994).
[3] Jan Mayer; “Alternative Weighted Dropping Strategies for ILUTP,” SIAM Journal on Scientific Computing, vol. 27, no. 4, pp.1424-1437, (2006).
[4] Yong Zhang, Ting-Zhu Huang, Yan-Fei Jing and Liang Li; “Flexible incomplete Cholesky factorization with multi- parameters to control the number of nonzero elements in preconditioners”, Numerical Linear Algebra with Applications, vol. 19, Issue 3, pp.555-569, (2012).
