Polynomial Eigenvalue Problem with few non-zero coefficients

Question

Let us define a diagonal matrix $\mathbf{D}(\lambda) = diag(\lambda^{m_1}, \dots, \lambda^{m_n})$ with $\lambda\in\mathbb{C}$ and positive integers $m_1, \dots, m_n$. The generalized characteristic polynomial of a $k \times k$ matrix $\mathbf{A}$ is then: $$ p(\lambda) = det(\mathbf{D}(\lambda) - \mathbf{A})$$

The order of $p(\lambda)$ is $N = \sum_{i=1}^n m_i$. It is known that all $m_i \gg k$ and all roots of $p(\lambda)$ are within the unit circle.

Is there an efficient numerical method to compute all eigenvalues?

This problem can be stated as a polynomial eigenvalue problem $$ (\lambda^{m_1} \mathbf{E}_1 + \dots + \lambda^{m_n} \mathbf{E}_n - \mathbf{A}) x = 0,$$ where $\mathbf{E}_i$ is zero except 1 at entry $[i,i]$. Is it possible to linearize this problem only with the non-zero coefficients such that the resulting generalized eigenvalue problem is of size $kn$? As $kn \ll N$, it might be superior to solve $p(z)$.

Answer 1

You may want to have a look at the research by Bini and coauthors on the Ehrlich-Aberth method, e.g., https://arxiv.org/abs/1207.6292. That method is sort-of "black box", i.e., you only need a way to evaluate and factor the matrix polynomial.