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 method is implemented in a freely available software package called ARPACK, and used successfully in a number of different applications. The convergence of the algorithm 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. Embree constructed a class of matrices for which the algorithm fails to converge, even in the exact arithmetic: the desired eigenvector is deflated out of the search space. A key property that ensures the failure is the non-normality of the example matrices. 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 in Sorensen’s proof. 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 values in the normal case.

matrix eigenvalue problem; normal matrix; Krylov subspace; Ritz values

nije evidentirano