Iterative methods for nearly singular linear systems

Iterative methods are developed and studied for near-singular linear system s Cx = b. Our approach, called the transformed minimal residual algorithm ( TMRES), is derived from any convergent iterative scheme Sx(k+1) = Tx(k) + b associated with a splitting C = S-T. In each step of TMRES, the transforme d residual S-1 (b-Cx) is minimized over a Krylov space generated by S-1T. T he original iterative scheme typically converges slowly when C is nearly si ngular, while a Krylov space generated by S-1T often contains a much better approximation to a solution. TMRES is algebraically equivalent to the gene ralized minimal residual algorithm (GMRES) preconditioned by S-1, although there are numerical differences since a different matrix S-1C is used to ge nerate the Krylov space in preconditioned GMRES. Special attention is given to sparsity and convergence issues related to linear systems of the form ( AA(T) +sigma I) x = b, where sigma greater than or equal to 0.