zbMATH — the first resource for mathematics

Recent advances on determining the number of real roots of parametric polynomials. (English) Zbl 0957.65041
The classical Sturm theorem is a convenient tool for determining the number of roots of a given polynomial in a certain range. However, today it is desirable to have a more general algorithm which can also deal with polynomials with symbolic or literal coefficients. The present paper is devoted to provide a complete discrimination system which could be used to determine the number of roots in some interval of a parametric real polynomial.
Recall that a complete discrimination system (CDS) is a set of explicit expressions in terms of the coefficients of the given polynomial, which is sufficient for determining the number and multiplicities of the roots, that is to say, to determine the complete root classification. The main ingredients are the discrimination matrix, the discrimination sequence, and the (revised) sign list.
As an application, the number of negative (positive) real roots of a polynomial is given in terms of the number of sign changes and the number of non-vanishing members of the (revised) sign list of the principal minor sequence associated with the polynomials discrimination matrix.

65H05 Numerical computation of solutions to single equations
12Y05 Computational aspects of field theory and polynomials (MSC2010)
26C10 Real polynomials: location of zeros
PDF BibTeX Cite
Full Text: DOI
[1] Arnon, D.S., Geometric reasoning with logic and algebra, Artif. intell., 37, 37-60, (1988) · Zbl 0705.68086
[2] Arnon, D.S.; Mignotte, M., On mechanical quantifier elimination for elementary algebra and geometry, J. symb. comput., 5, 237-260, (1988) · Zbl 0644.68051
[3] D. S. Arnon, S. Smith, Proceedings of EUROCAL’83, 1983, Springer, New York, 36, 44
[4] Char, B.W., Maple V library reference manual, (1991), Springer New York · Zbl 0763.68046
[5] Collins, G.E.; Hong, H., Partial cylindrical algebraic decomposition for quantifier elimination, J. symb. comput., 12, 299-328, (1991) · Zbl 0754.68063
[6] Gantmacher, F.R., Matrix theory, (1959), Chelsea Publishing Company New York · Zbl 0085.01001
[7] González-Vega, L., A combinatorial algorithm solving some quantifier elimination problems, (), 365-375 · Zbl 0900.68277
[8] L. González-Vega, H. Lombardi, T. Recio, M.-F. Roy, Proceedings of ISSAC’89, 1989, ACM Press, New York, 136, 146
[9] González-Vega, L.; Recio, T.; Lombardi, H.; Roy, M.-F., Sturm – habicht sequence, determinants and real roots of univariate polynomials, (), 300-316 · Zbl 0900.12002
[10] Habicht, W, Eine verallgemeinerung des sturmschen wurzelzählverfahrens, Comm. math. helv., 21, 99-116, (1948) · Zbl 0029.24402
[11] Lazard, D., Quantifier elimination: optimal solution for two classical examples, J. symb. comput., 5, 261-266, (1988) · Zbl 0647.03023
[12] Liang, S.X.; Zhang, J.Z., A complete discrimination system for polynomials with complex coefficients and its automatic generation, Sci. China, E42, (1999)
[13] Loos, R., Generalized polynomial remainder sequence, (), 115-137
[14] Roy, M.-F., Basic algorithms in real geometry and their complexity: from sturm’s theorem to the existential theory of reals, (), 1-68 · Zbl 0894.14028
[15] V. Weispfenning, Proceedings of ISSAC’94, 1994, ACM Press, New York, 258, 263
[16] Wu, W.T., On problems involving inequalities, MM research preprints, 7, 1-13, (1992)
[17] Yang, L.; Hou, X.R.; Zeng, Z.B., A complete discrimination system for polynomials, Sci. China, E 39, 628-646, (1996) · Zbl 0866.68104
[18] Yang, L.; Xia, B.C., Explicit criterion to determine the number of positive roots of a polynomial, MM research preprints, 15, 134-145, (1997)
[19] Yang, L.; Zhang, J.Z.; Hou, X.R., Non-linear equation systems and automated theorem proving (in Chinese), (1996), Shanghai Press of Science, Technology and Education Shanghai
[20] F. M. Zou, 1997, 60, 66
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.