A refined harmonic Rayleigh-Ritz procedure and an explicitly restarted refined harmonic Arnoldi algorithm (Q814247)

The authors consider the large matrix eigenproblem \[ A {\phi}_i = {\lambda}_i {\phi}_i, \quad A \in {\mathcal{C}}^{n \times n} \quad\text{ nonsingular}, \] where \(({\phi}_i, {\lambda}_i)\) are the eigenpairs of \(A\). The aim is to compute \(l\) eigenpairs, usually being those with the smallest or largest magnitude or with the smallest or largest real part. The basis of the well-known iterative methods (Arnoldi method, subspace iteration, Jacobi-Davidson method as well as their variants) is the Rayleigh-Ritz procedure. First a short history of the subject is given in the Introduction. In an earlier paper \textit{Zh. Jia} and \textit{G. W. Stewart} [Math. Comput. 70, No.~234, 637--647 (2001 ; Zbl 0968.65020)] have shown that under certain conditions there are Ritz values that converge to the desired eigenvalues but the corresponding Ritz vectors may fail to converge, and they developed so-called ``refined'' methods for the Arnoldi method, the Rayleigh-Ritz procedure, the block Arnoldi method, the subspace iteration, the Jacobi-Davidson method and the shift-and-invert Arnoldi method that correct the possible nonconvergence. The new methods are very often much more efficient, particularly for difficult problems. \textit{Zh. Jia} [Appl. Numer. Math. 42, No.~4, 489--512 (2002; Zbl 1030.65023)] improved also the implicitly restarted harmonic Arnoldi algorithm (IRHA) created by \textit{R. B. Morgan} [SIAM J. Matrix Anal. Appl. 21, 1112--1135 (2000; Zbl 0963.65038)], introducing certain refined shifts. The resulting method is called implicitly restarted refined harmonic Arnoldi algorithm (IRRHA). The present paper consists of four parts. First, the authors consider the harmonic Rayleigh-Ritz procedure, which retains harmonic Ritz values and computes refined harmonic Ritz vectors. A derived a priori error bound shows that the refined harmonic Ritz vector converge if the harmonic Ritz value does. Second, the refined harmonic Arnoldi method is introduced (algorithm 1). Third, the restarting issue of the refined harmonic Arnoldi method (algorithm 1) is treated. Instead of an implicit restarting an explicit restarting is introduced. The restarting vector is chosen using an augmented Krylov subspace (algorithm 2). Finally, numerical results show that algorithm 2 for very sparse matrices is considerably superior to IRHA and at least competitive with IRRHA. For not very sparse matrices and \(l \geq 20\) IRRHA is more efficient. The order \((n = 822\) until \(n=10000)\) of the sparse test matrices is rather moderate.