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)$.



Polynomial Eigenvalue Problem with few non-zero coefficients
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.


