engleski

On the Ritz Values of Normal Matrices

The implicitly restarted Arnoldi method (IRAM) introduced by Sorensen is a well-known algorithm for computing a few eigenpairs of a large, generally non-symmetric sparse matrix. The eigenvalue approximations in this algorithm are usually taken as the Ritz or the harmonic values computed from a Krylov subspace. The convergence of the IRAM has been a subject of intensive study. While Sorensen proved the convergence when the algorithm is used to compute the extreme eigenvalues of Hermitian matrices, the conditions for the convergence in the general case are still unknown. In particular, Embree constructed a class of matrices for which the algorithm fails to converge, even in the exact arithmetic. A key property that ensures the failure is the non-normality of the example matrices. Furthermore, Tebbens et al. show that an arbitrary convergence history for the Arnoldi method is possible. In our talk, we discuss the convergence of IRAM for normal matrices. We demonstrate the difficulty in keeping the monotonicity of the Ritz values, which was essential for the convergence in the Hermitian case. A simple condition for a set of complex numbers to appear as Ritz values of a normal matrix is given: it is necessary and sufficient that a certain Cauchy matrix has a positive vector in its kernel. This fact is then used to explore the more complex geometry of Ritz and harmonic Ritz values in the normal case, which in turn has implications on the IRAM's convergence. We also present a variant of the Cauchy interlacing lemma.

eigenvalues; Ritz values; Krylov subspaces; normal matrices

nije evidentirano