Deflated And Augmented Krylov Subspace Methods

This paper is concerned with deflated and augmented Krylov subspace methods for solving the large systems of linear equations. It is well known that the convergence of Krylov subspace methods depends to a large degree on the distribution of eigenvalues of the coefficient matrix. If there are small eigenvalues, then removing or deflating them can greatly improve the convergence rates. Likewise, for the problem of computing an eigenvalue, deflating nearby eigenvalues is helpful. One way that eigenvalues can been deflated is for the corresponding eigenvectors to be in the subspace. Once a Krylov subspace grows big enough, some deflation occurs automatically. However, restarted methods may not develop a large enough Krylov subspace for this automatic deflation, arid convergence then suffers accordingly. Also, even if approximate eigenvectors do develop that are accurate enough for deflation, they only for that cycle and may need to be developed after a restart . The augmented Krylov subspace methods include the approximate eigenvectors determined from the previous subspace in the new subspace. This deflates the small eigenvalues and thus improve the convergence. In this paper, we introduce the augmented Krylov subspace methods algorithms and give the results on the convergence of the augmented Krylov subspace methods. These methods are equivalent to each other, but their implements are diffierent. We also compare their implements. In this paper, we focus on applying the deflated and augmented Krylov subspace technique to solving the Sylvester equation and the generalized Sylvester equation. By our knowledge, these methods in this paper should be the first kind of accelerated methods for solving the Sylvester equation and the generalized Sylvester equation. Numerical experiments in the last chapter show that the augmented Krylov subspace methods are very efficient.