Polynomial eigenvalue problems are often found in scientific computing applications. When the coefficient matrices of the polynomial are large and sparse, usually only a few eigenpairs are required and projection methods are the best choice. We focus on Krylov methods that operate on the companion linearization of the polynomial but exploit the block structure with the aim of being memory-efficient in the representation of the Krylov subspace basis. The problem may appear in the form of a low-degree polynomial (quartic or quintic, say) expressed in the monomial basis, or a high-degree polynomial (coming from interpolation of a nonlinear eigenproblem) expressed in a nonmonomial basis. We have implemented a parallel solver in SLEPc covering both cases that is able to compute exterior as well as interior eigenvalues via spectral transformation. We discuss important issues such as scaling and restart and illustrate the robustness and performance of the solver with some numerical experiments., The first author was supported by the Spanish Ministry of Education, Culture and Sport through an FPU grant with reference AP2012-0608.

Methods for the polynomial eigenvalue problem sometimes need to be followed by an iterative refinement process to improve the accuracy of the computed solutions. This can be accomplished by means of a Newton iteration tailored to matrix polynomials. The computational cost of this step is usually higher than the cost of computing the initial approximations, due to the need of solving multiple linear systems of equations with a bordered coefficient matrix. An effective parallelization is thus important, and we propose different approaches for the message-passing scenario. Some schemes use a subcommunicator strategy in order to improve the scalability whenever direct linear solvers are used. We show performance results for the various alternatives implemented in the context of SLEPc, the Scalable Library for Eigenvalue Problem Computations., This work was partially supported by the Spanish Ministry of Economy and Competitiveness under grant TIN2013-41049-P. Carmen Campos was supported by the Spanish Ministry of Education, Culture and Sport through an FPU grant with reference AP2012-0608. The computational experiments of Section 5 were carried out on the supercomputer Tirant at Universitat de Valencia.

We investigate how to adapt the Q-Arnoldi method for the case of symmetric quadratic eigenvalue problems, that is, we are interested in computing a few eigenpairs of with M, C, K symmetric matrices. This problem has no particular structure, in the sense that eigenvalues can be complex or even defective. Still, symmetry of the matrices can be exploited to some extent. For this, we perform a symmetric linearization , where A, B are symmetric matrices but the pair (A, B) is indefinite and hence standard Lanczos methods are not applicable. We implement a symmetric-indefinite Lanczos method and enrich it with a thick-restart technique. This method uses pseudo inner products induced by matrix B for the orthogonalization of vectors (indefinite Gram-Schmidt). The projected problem is also an indefinite matrix pair. The next step is to write a specialized, memory-efficient version that exploits the block structure of A and B, referring only to the original problem matrices M, C, K as in the Q-Arnoldi method. This results in what we have called the Q-Lanczos method. Furthermore, we define a stabilized variant analog of the TOAR method. We show results obtained with parallel implementations in SLEPc., This work was supported by the Spanish Ministry of Economy and Competitiveness under Grant TIN2013-41049-P. Carmen Campos was supported by the Spanish Ministry of Education, Culture and Sport through an FPU Grant with reference AP2012-0608.