A recursive algorithm for constructing generalized Sturm sequence. (English) Zbl 0984.12008

As is known, a generalized Sturm sequence (GSS), as well as the classical Sturm sequence, plays a very important role in real roots classification of algebraic equations, but it is very difficult to compute it with symbolic coefficients.
L. González-Vega, T. Reico, H. Lombardi and M.-F. Roy [Caviness (ed.) et al., Quantifier elimination and cylindrical algebraic decomposition, 300-316 (1998; Zbl 0900.12002)] introduced the Sturm-Habicht sequence which generalized the work of W. Habicht [Comment. Math. Helv. 21, 99-116 (1948; Zbl 0029.24402)]. Although the above sequence is easier to compute compared with the conventional approach, such a sequence is not the Sturm sequence in the usual sense because there might be zero-polynomials in this sequence.
In this paper, the authors use a recursive method to construct GSS for two parametric polynomials via the subresultant polynomial chain of the two polynomials avoiding complicated division operations. They establish a connection between GSS and the subresultant polynomial chain of two polynomials and an algorithm that computes the leading coefficients and degrees of the GSS for the infinite interval case. The algorithm has been implemented in Maple and is efficient for constructing the leading terms of the GSS for polynomials with symbolic coefficients.


12Y05 Computational aspects of field theory and polynomials (MSC2010)
12D10 Polynomials in real and complex fields: location of zeros (algebraic theorems)
13P99 Computational aspects and applications of commutative rings


Full Text: DOI


[1] Tarski, A., A Decision Method for Elementary Algebra and Geometry, 2nd ed., Univ. of California Press, 1951. · Zbl 0044.25102
[2] González-Vega, L., Lombardi, H., Recio, T. et al., Sturm-Habicht sequence, ISSAC-89 Proceedings, ACM Press, 1989, 136–146.
[3] González-Vega, L., Recio, T., Lombardi, H. et al., Sturm-Habicht sequence, determinants and real roots of univariate polynomials, Quantifier Elimination and Cylindrical Algebraic Decomposition (eds. Caviness, B. F., Johnson, J. R.), Berlin: Springer-Verlag, 1998, 300–316. · Zbl 0900.12002
[4] Habicht, W., Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens, Comm. Math. Helvetici, 1948, 21: 99. · Zbl 0029.24402 · doi:10.1007/BF02568028
[5] Yang, L., Hou, X. R., Zeng, Z. B., A complete discrimination system for polynomials, Science in China, Ser. E, 1996, 39(6): 628. · Zbl 0866.68104
[6] Yang, L., Xia, B. C., Explicit criterion to determine the number of positive roots of a polynomial, MM Research Preprints, 1997, (15): 134.
[7] Yang, L., Zhang, J. Z., Hou, X. R., Nonlinear Algebraic Equation System and Automated Theorem Proving (in Chinese), Shanghai: Shanghai Scientific and Technological Education Publishing House, 1996.
[8] Liang, S. X., Zhang, J. Z., A complete discrimination system for polynomials with complex coefficients and its automatic generation, Science in China, Ser. E, 1999, 42(2): 113. · Zbl 0949.12002 · doi:10.1007/BF02917106
[9] Loos, R., Generalized polynomial remainder sequence, Computer Algebra: Symbolic and Algebraic Computation (ed. Buchberger, B.), Berlin: Springer-Verlag, 1983, 115–137.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.