The idea behind Krylov methods.

*(English)*Zbl 0982.65034Introduction: 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 can be 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 a 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.

Our discussion demonstrates that eigenvalues play a central role when it comes to ensuring existence and uniqueness of Krylov solutions; they are not merely an artifact of convergence analyses.

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 a 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.

Our discussion demonstrates that eigenvalues play a central role when it comes to ensuring existence and uniqueness of Krylov solutions; they are not merely an artifact of convergence analyses.

##### MSC:

65F10 | Iterative numerical methods for linear systems |

65F20 | Numerical solutions to overdetermined systems, pseudoinverses |