Lecture on Numerical Linear Algebra

10-11am, November 4th (Tuesday)
Seminar Room 1 (2006), 20th floor, NII

Dr. Keiichi Morikuni
Institute of Computer Science
Academy of Sciences of the Czech Republic

Title
Inner-iteration preconditioning for singular linear systems

Abstract
For solving large sparse linear systems of equations, iterative methods are preferred in terms of efficiency and memory requirement. When the problem is ill-conditioned, the convergence of iterative methods tends to be slow and the convergence may be accelerated by preconditioning. However, in the singular case, iterative methods and preconditioners may fail to converge and break down. We give a necessary and sufficient condition under which the generalized minimal residual (GMRES) method finds a solution of linear systems of equations with an arbitrary index without breakdown and characterize the solution. Next, we apply this result to GMRES preconditioned by several steps of a stationary iterative method performed as inner iterations, and present theoretical justifications for using this method and classes of stationary iterative methods that can be used for inner-iteration preconditioning. Finally, numerical experiments on large sparse linear systems show that the method outperforms previous methods.

URL