**In minisymposium: Tropical Algebra in Numerical Linear Algebra**

Let $P(z)$ be a $s \times s$ matrix polynomial of degree $d$.
The *polynomial eigenvalue problem* (PEP) is to
look for nonzero vectors $v$ (right eigenvectors) and corresponding eigenvalues $\lambda$
such that $P(\lambda) v = 0$.

The standard way of solving the PEP is via *linearization*, that is, by
constructing a $ds\times ds$ matrix polynomial $L(z)$ of degree one such that
$$
E(z) L(z) F(z) =
\left[
\begin{array}{cc}
P(z) & 0 \\
0 & I_{(d-1)s}
\end{array}
\right]
$$
with $E(z)$ and $F(z)$ unimodular matrix polynomials.
Then clearly $P(z)$ and $L(z)$ have the same eigenvalues.
Many linearizations have been proposed in the literature
based on the basis in which $P(z)$ is represented,
e.g., degree graded bases
such as the monomial basis, the Chebyshev basis, \ldots, or interpolation bases,
such as the Lagrange polynomials.
Companion linearizations are commonly used in practice for matrix polynomials
expressed in the monomial basis but
these are known to affect the sensitivity of eigenvalues and, when used with
numerically stable eigensolvers for generalized eigenproblems,
they can compute eigenpairs for $P$ with large backward errors
unless the linear problem is solved several times with different scalings
of the eigenvalue parameter.

The matrix polynomial $P(z)$ is uniquely determined by its values $P_i$ in $d$ points $\sigma_i$, $i = 1,2,\ldots,d$ and its highest degree coefficient $P_d$. A Lagrange-type linearization based on this representation is $$ L(z)= \left[ \begin{array}{c|ccc} P_d &P(\sigma_1)&\cdots&P(\sigma_d)\\\hline -\beta_1I_{s}&(z-\sigma_1)I_{s}& & \\ \vdots& &\ddots& \\ -\beta_{d}I_{n}& & &(z-\sigma_{d})I_{n} \end{array} \right], $$ where the $\beta_i$ are the so-called barycentric weights.

We show that for a particular choice of the interpolation points $\sigma_i$, this linearization combined with an appropriate scaling is well suited for the computation of all the eigenvalues of $P$ with the QZ algorithm even when the eigenvalues have a large variation in magnitude.