Deliberate Ill-Conditioning of Krylov Matrices

Abstract

This paper starts o with studying simple extrapolation methods for the classical iteration schemes such as Richardson, Jacobi and Gauss-Seidel iteration. The extrapolation procedures can be interpreted as approximate minimal residual methods in a Krylov subspace. It seems therefore logical to consider, conversely, classical methods as pre-processors for Krylov subspace methods, as was done by Ztko (1996) for the Conjugate Gradient method. The observation made by Ipsen (1998) that small residuals necessarily imply an ill-conditioned Krylov matrix, explains the success of such pre-processing schemes: residuals of classical methods are (unscaled) power method iterates, and building a Krylov subspace on such a classical residual will therefore lead to expansion vectors that are at small angle to the previous Krylov vectors. This results in an ill-conditioned Krylov matrix. In this paper, we present a largenumber of experiments that support this claim, and give theoretical interpretations of the pre-processing. The results are mainly of interest in Krylov subspace methods for non-Hermitian matrices based on long recurrences, and in particular for applications with heavy memory limitations. Also, in applications in which minimal residual methods stagnate due to a lack of ill-conditioning, the use of a classical preprocessor can be a cheap and easily parallelizable remedy.