An improved grid method for the computation of the pseudospectra of matrix polynomials∗

Pseudospectra of matrix polynomials have been systematically investigated in the last years, since they provide important insights into the sensitivity of poly-nomial eigenvalue problems. An accurate approximation of the pseudospectrum of a matrix polynomial P (λ) by means of the standard grid method is computa-tionally high demanding. In this paper, we propose an improvement of the grid method, which reduces the computational cost and retains the robustness and the parallelism of the method. In particular, after giving two lower bounds for the distance from a point to the boundary of the pseudospectrum of P (λ), we present two algorithms for the estimation of the pseudospectrum, using exclusion discs. Furthermore, two illustrative examples and an application of pseudospectra on elliptic (quadratic) eigenvalue problems are given