ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Tropical Algebra in Numerical Linear Algebra

Thu 11:30–12:00, Room AV 01.12
Solving polynomial eigenvalue problems by a Lagrange-type linearization
Marc Van Barel (KU Leuven)
Joint work with Françoise Tisseur (University of Manchester)

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.