第37回 数値解析セミナー

2012年7月31日（火）16:30-18:00
東京大学工学部6号館3階セミナー室C (372号室)

保國 惠一（総合研究大学院大学 複合科学研究科 情報学専攻）

大規模最小二乗問題に対する内部反復前処理付きGMRES法
GMRES methods with inner-iteration preconditioning for large least squares problems

The conventional methods for solving large least squares problems such as the CGLS and LSQR methods suffer from slow convergence for ill-conditioned problems. Then, one can use a technique called preconditioning to accelerate the convergence. Conventional preconditioners require CPU time and memory for computing factors of a preconditioning matrix. In this talk, we introduce inner-iteration preconditioning using stationary iterative methods, and show that a sufficient condition under which the generalized minimal residual method (GMRES) preconditioned with the inner iterations determines a least squares solution without breakdown is that the iteration matrix is semi-convergent. This condition is satisfied by the Jacobi and successive overrelaxation (SOR) methods applied to the normal equations. Moreover, we analyse the spectrum of the preconditioned matrix. Finally, numerical experiments show that the method is superior to previous methods, especially for ill-conditioned and rank-deficient problems.

Further information