An Inexact Shift-and-Invert Arnoldi Algorithm for Large Non-Hermitian Generalised Toeplitz Eigenproblems

Abstract

The shift-and-invert Arnoldi method is a most effective approach to compute a few eigenpairs of a large non-Hermitian Toeplitz matrix pencil, where the Gohberg-Semencul formula can be used to obtain the Toeplitz inverse. However, two large non-Hermitian Toeplitz systems must be solved in the first step of this method, and the cost becomes prohibitive if the desired accuracy for this step is high — especially for some ill-conditioned problems. To overcome this difficulty, we establish a relationship between the errors in solving these systems and the residual of the Toeplitz eigenproblem. We consequently present a practical stopping criterion for their numerical solution, and propose an inexact shift-and-invert Arnoldi algorithm for the generalised Toeplitz eigenproblem. Numerical experiments illustrate our theoretical results and demonstrate the efficiency of the new algorithm.