The complete root classification of a parametric polynomial on an interval

ABSTRACT

Given a real parametric polynomial p(x) and an interval (a,b) ⊂ R, the Complete Root Classification (CRC) of p(x) on (a,b) is a collection of all possible cases of its root classification on (a,b), together with the conditions its coefficients must satisfy for each case. In this paper, a new algorithm is proposed for the automatic computation of the complete root classification of a parametric polynomial on an interval. As a direct application, the new algorithm is applied to some real quantifier elimination problems.

REFERENCES

• 1: Hitoshi Yanami , Hirokazu Anai, SyNRAC: a maple toolbox for solving real algebraic constraints, ACM Communications in Computer Algebra, v.41 n.3, September 2007 issue 161 [doi>10.1145/1358190.1358205]
• 2: Dennis S. Arnon, Geometric reasoning with logic and algebra, Artificial Intelligence, v.37 n.1-3, p.37-60, Dec. 1988 [doi>10.1016/0004-3702(88)90049-5]
• 3: Saugata Basu , Richard Pollack , Marie-Françoise Roy, Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: Attilio Colagrossi , Alfonso M. Miola, Computing real zeros of polynomials with parametric coefficients, ACM SIGSAM Bulletin, v.17 n.1, p.12-15, February 1983 [doi>10.1145/1089320.1089322]
• 5: S. Liang and D. J. Jeffrey. An Algorithm for computing the complete root classification of a parametric polynomial. Lecture Notes in Computer Science,4120:116--130,2006.
• 6: S. Liang and D. J. Jeffrey. The automatic computation of the complete root classification for a parametric polynomial. Electronic proceedings of MEGA 2007,www.ricam.oeaw.ac.at/mega2007/electronic/30.pdf .
• 7: S. Liang and J. Zhang. A complete discrimination system for polynomials with complex coefficients and its automatic generation. Science in China (Series E), 42(2):113--128, 1999.
• 8: F. Rouillier. On solving parametric systems.In Workshop on Challenges in Linear and Polynomial Algebra in Symbolic Computation Software. Banff International Research Center, 2005.
• 9: Lu Yang, Recent advances on determining the number of real roots of parametric polynomials, Journal of Symbolic Computation, v.28 n.1-2, p.225-242, July/Aug. 1999 [doi>10.1006/jsco.1998.0274]
• 10: L. Yang, X. Hou, and Z. Zeng. Complete discrimination system for polynomials. Science in China (Series E), 39(6):628--646, 1996.
• 11: L. Yang and B. Xia. Explicit criterion to determine the number of positive roots of a polynomial. MM Research Preprints, 15:134--145, 1997.
• 12: L. Yang and B. Xia. Quantifier elimination for quartics. Lecture Notes in Computer Science,4120:131--145,2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms

Keywords:
complete root classification, interval, parametric polynomial, real quantifier elimination, real root