The Idea Behind Krylov Methods

ABSTRACT

We explain why Krylov methods make sense, and why it is natural to represent a solution to a linear system as a member of a Krylov space. In particular we show that the solution to a nonsingular linear system Ax = b lies in a Krylov space whose dimension is the degree of the minimal polynomial of A. Therefore, if the minimal polynomial of A has low degree then the space in which a Krylov method searches for the solution is small. In this case a Krylov method has the opportunity to converge fast. When the matrix is singular, however, Krylov methods can fail. Even if the linear system does have a solution, it may not lie in a Krylov space. In this case we describe the class of right-hand sides for which a solution lies in a Krylov space. As it happens, there is only a single solution that lies in a Krylov space, and it can be obtained from the Drazin inverse. Prof. Ipsen's work was supported in part by the National Science Foundation under grants CCR-9102853 and CCR-9400921, and Prof. Meyer's work was supported in part by the National Science Foundation under grants DMS-9020915 and DMS-9403224.

JOURNAL

American Mathematical Monthly

Vol. 105, No. 10, December, 1998, pp. 889-899.

CO-AUTHORS

Ilse C. F. Ipsen

Carl D. Meyer

THE POSTSCRIPT FILE

The postscript file (uncompressed) for the entire paper is 768K.

To receive it, click on Krylov.ps

THE PDF FILE

To receive the PDF file, click on Krylov.pdf (576K)

Return To Abstracts