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

Pseudospectra of matrix polynomials have been systematically investigated in recent years, since they provide important insights into the sensitivity of polynomial eigenvalue problems. An accurate approximation of the pseudospectrum of a matrix polynomial $P\left(\lambda \right)$ by means of the standard grid method is highly demanding computationally. 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\left(\lambda \right)$, 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.