Shift-and-invert Arnoldi for singular eigenvalue problems
Karl Meerbergen, Zhijun Wang
Abstract
The solution of the regular \(n\times n\) generalized eigenvalue problem \(Ax=\lambda Bx\) is pretty well understood. This is not so for singular pencils, i.e., pencils for which \(A-\lambda B\) is singular for any \(\lambda \in \mathbb {C}\cup \{\infty \}\). We say that \(\lambda \) is an eigenvalue iff the rank of \(A-\lambda B\) is below the normal rank, i.e., the maximum rank of \(A-\sigma B\) for \(\sigma \in \mathbb {C}\cup \{\infty \}\).
The staircase method separates the regular and singular parts of the pencil using the Kronecnker canonical form. The QZ method can also perform such a separation but may suffer from numerical instabilities. Recently, a rank perturbation was proposed [1][2] which is related to a bordered regular pencil. In this talk, we use a border of the form
\[ \begin {bmatrix} A - \lambda B & W \\ V^T & 0 \end {bmatrix} \]
where \(W\) and \(V\) are chosen so that both
\[ \begin {bmatrix} A - \lambda B & W \end {bmatrix} \quad \text {and}\quad \begin {bmatrix} A - \lambda B \\ V^T \end {bmatrix} \]
have rank \(n\) for all \(\lambda \). This bordered eigenvalue problem has a spurious infinite eigenvalue, and may have spurious finite eigenvalue too, but for every eigenvector a simple test can be performed to check whether the eigenvalue is true or spurious.
The aim is to solve the bordered eigenvalue problem using the shift-and-invert Arnoldi method. We employ a special inner product and implicit restarting to reduce the impact of the infinite eigenvalue. To determine a suitable \(V\) and \(W\) we propose a rank revealing LU factorization that should enable computations for large sparse problems. We illustrate the algorithm and the theory for problems arising from multiparameter eigenvalue problems, rectangular pencils and singular quadratic eigenvalue problems.
References
-
[1] M. E. Hochstenbach, C. Mehl, and B. Plestenjak. Solving singular generalized eigenvalue problems by a rank-completing perturbation. SIAM Journal on Matrix Analysis and Applications, 40(3):1022–1046, January 2019.
-
[2] M. E. Hochstenbach, C. Mehl, and B. Plestenjak. Solving singular generalized eigenvalue problems. part ii: Projection and augmentation. SIAM Journal on Matrix Analysis and Applications, 44(4):1589–1618, October 2023.