Hyperbolic quadratic matrix polynomials Q(λ)=λ2A+λB+C are an important
class of Hermitian matrix polynomials with real eigenvalues, among which the overdamped quadratics
are those with nonpositive eigenvalues. Neither the definition of overdamped nor any of the standard
characterizations provides an efficient way to test if a given Q has this property. We show that
a quadratically convergent matrix iteration based on cyclic reduction, previously studied by Guo
and Lancaster, provides necessary and sufficient conditions for Q to be overdamped. For weakly
overdamped Q the iteration is shown to be generically linearly convergent with constant at worst
1/2, which implies that the convergence of the iteration is reasonably fast in almost all cases of
practical interest. We show that the matrix iteration can be implemented in such a way that when
overdamping is detected a scalar μ<0 is provided that lies in the gap between the n largest and n smallest eigenvalues of the n×n quadratic eigenvalue problem (QEP) Q(λ)x=0. Once such a
μ is known, the QEP can be solved by linearizing to a definite pencil that can be reduced, using
already available Cholesky factorizations, to a standard Hermitian eigenproblem. By incorporating
an initial preprocessing stage that shifts a hyperbolic Q so that it is overdamped, we obtain an
efficient algorithm that identifies and solves a hyperbolic or overdamped QEP maintaining symmetry
throughout and guaranteeing real computed eigenvalues.