The shift-and-invert Arnoldi method for singular matrix pencils
For researchers solving large sparse singular eigenvalue problems, this provides a more efficient and accurate regularization approach.
The paper extends the shift-and-invert Arnoldi method to singular matrix pencils by proposing sparse regularization matrices derived from sparse LU factorization pivoting, which preserves sparsity and improves performance and accuracy compared to randomized regularization methods.
A popular method for solving large sparse regular eigenvalue problem is the shift-and-invert Arnoldi method. This paper aims to use the method for large sparse singular pencils. In three recent papers, {\em Hochstenbach, Mehl, and Plestenjak, 2019, 2023, and 2024}, propose regularization of the singular pencil, using randomly chosen regularization matrices. We propose sparse regularization matrices obtained from the pivoting sequence of a sparse LU factorization. As a side effect, the LU factorization often is rank revealing, which facilitates finding a regularization. Numerical examples illustrate that the LU factorization mostly detects the normal rank and finds a suitable sparse regularization. A rank correction method is proposed for the cases where the normal rank is not determined correctly. For full rank rectangular eigenvalue problems, the pivoting sequence of existing sparse direct system solvers can be used. We compare with randomized regularization methods: preservation of sparsity is beneficial for performance, and often, the accuracy of the eigenvalue solver.