Algorithms for hyperbolic quadratic eigenvalue problems

We consider the quadratic eigenvalue problem (or the QEP) $(\lambda^2 A+\lambda B + C)x=0$, where $A, B,$ and $C$ are Hermitian with $A$ positive definite. The QEP is called hyperbolic if $(x^*Bx)^2>4(x^*Ax)(x^*Cx)$ for all nonzero $x\in {\mathbb C}^n$. We show that a relatively efficient test for hyperbolicity can be obtained by computing the eigenvalues of the QEP. A hyperbolic QEP is overdamped if $B$ is positive definite and $C$ is positive semidefinite. We show that a hyperbolic QEP (whose eigenvalues are necessarily real) is overdamped if and only if its largest eigenvalue is nonpositive. For overdamped QEPs, we show that all eigenpairs can be found efficiently by finding two solutions of the corresponding quadratic matrix equation using a method based on cyclic reduction. We also present a new measure for the degree of hyperbolicity of a hyperbolic QEP.