Compact Two-Sided Krylov Methods for Nonlinear Eigenvalue Problems

Abstract

We describe a generalization of the compact rational Krylov (CORK) methods for polynomial and rational eigenvalue problems that usually, but not necessarily, come from polynomial or rational approximations of genuinely nonlinear eigenvalue problems. CORK is a family of one-sided methods that reformulates the polynomial or rational eigenproblem as a generalized eigenvalue problem. By exploiting the Kronecker structure of the associated pencil, it constructs a right Krylov subspace in compact form and thereby avoids the high memory and orthogonalization costs that are usually associated with linearizations of high degree matrix polynomials. CORK approximates eigenvalues and their corresponding right eigenvectors but is not suitable in its current form for the computation of left eigenvectors. Our generalization of the CORK method is based on a class of Kronecker structured pencils that include as special cases the CORK pencils, the transposes of CORK pencils, and the symmetrically structured linearizations by Robol, Vandebril, and Van Dooren [SIAM J. Matrix Anal. Appl., 38 (2017), pp. 188--216]. This class of structured pencils facilitates the development of a general framework for the computation of both right- and left-sided Krylov subspaces in compact form, and hence allows the development of two-sided compact rational Krylov methods for nonlinear eigenvalue problems. The latter are particularly efficient when the standard inner product is replaced by a cheaper to compute quasi-inner product. We show experimentally that convergence results similar to CORK can be obtained for a certain quasi-inner product.