Computationally efficient applications of the Euclidean algorithm to zero location (Q2564899)

The author presents a characterization of the inertia of the \(n\times n\) Hankel matrix associated with a pair of real polynomials \(p(x)\) and \(q(x)\) in terms of the leading coefficients and the degree of the quotients generated by the Euclidean algorithm applied to \(p(x)\) and \(q(x)\). In this way, classical zero-location results which rely on the evaluation of the inertia of quadratic forms can be reformulated in terms of polynomials generated as quotients by the Euclidean algorithm. All the quotients generated by the Euclidean scheme applied by \(p(x)\) and \(q(x)\) can be computed at the overall cost of \(O(n^2)\) arithmetic operations, which can be reduced to \(O(n\log^2n)\) arithmetic operations by combining fast polynomial arithmetic and divide-and-conquer techniques. The characterization finds applications to the solution of both Routh-Hurwitz and Schur-Cohn problems. Moreover, it can be used for computing the different real zeros of a real polynomial in an interval.