Optimal Fraction-Free Routh Tests for Complex and Real Integer Polynomials

The Routh test is the simplest and most efficient algorithm to determine whether all the zeros of a polynomial have negative real parts. However, the test involves divisions that may decrease its numerical accuracy and are a drawback in its use for various generalized applications. The paper presents fraction-free forms for this classical test that enhance it with the property that the testing of a polynomial with Gaussian or real integer coefficients can be completed over the respective ring of integers. Two types of algorithms are considered one, named the G-sequence, which is most efficient (as an integer algorithm) for Gaussian integers, and another, named the R-sequence, which is most efficient for real integers. The G-sequence can be used also for the real case, but the R-sequence is by far more efficient for real integer polynomials. The count of zeros with positive real parts for normal polynomials is also presented for each algorithm.