Computing real zeros of polynomials with parametric coefficients

ABSTRACT

The problem of localizing real zeros of polynomials with parametric coefficients is considered.An informative solution to this problem is proposed and an algorithm based on a generalization of Sturm's method for univariate polynomials over the reals is presented. Thus, given a polynomial P(x,y), where x is the variable and y a parameter, and a real interval Ix for the variable x, the algorithm furnishes a list (eventually empty) of real intervals Iiy for the parameter y, such that there exist i real simple zeros of P(x,y) in the two dimension interval determined by Ix and Iiy.

REFERENCES

• 1: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 2: R. T. Gregory: Error-free computation with rational numbers, BIT 21(1981), 194--202.
• 3: Lee E. Heindel, Integer Arithmetic Algorithms for Polynomial Real Zero Determination, Journal of the ACM (JACM), v.18 n.4, p.533-548, Oct. 1971 [doi>10.1145/321662.321667]
• 4: Alfonso M. Miola, The conversion of Hensel codes to their rational equivalents: or how to solve the Gregory's open problem, ACM SIGSAM Bulletin, v.16 n.4, p.24-26, November 1982 [doi>10.1145/1089310.1089316]
• 5: M. O. Rabin: Probabilistic algorithm in finite field, SIAM J. Comp., vol. 9, n. 2, May '80.
• 6: J. V. Uspensky: Theory of equations; Mc Graw-Hill, New York, 1948.