Spécialisation de la suite de Sturm et sous-résultants. I. (Specialization of the Sturm sequence and subresultants. I). (French) Zbl 0732.68059

This paper is the first one of a series of two devoted to the specialization of the Sturm sequence and the subresultants. Sturm sequences allow to compute the number of roots of a polynomial and generalized Sturm sequences to compute the number of real roots of a polynomial verifying a given polynomial inequality. It is desirable in computer algebra to design improvements of Sturm sequences for which it is possible to control the growth of the computation and to avoid denominators in order to be able to specialize the coefficients.
The first part contains the definition and properties of the generalized Sturm sequence and explains why its behaviour under specialization is bad.
The second part contains a developed, precise and detailed analysis of the theory of subresultants (correcting some errors in the literature). The subresultants are polynomials proportional to the polynomials in the sequence of the remainders of the Euclidean algorithm. Their coefficients are defined in determinants, hence their computation can be done with a good control of the coefficients growth in indeterminate computations and they enjoy a good behaviour under specialization. Precise algorithms in order to compute them efficiently are described and discussed.
Reviewer: L.González-Vega


68W30 Symbolic computation and algebraic computation
12D10 Polynomials in real and complex fields: location of zeros (algebraic theorems)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI EuDML


[1] 1. A. C. AITKEN, On te Evaluation of Determinants, the Formation of their Adjugates, and the Practical Solution of Simultaneous Linear Equations, Proc. Edinburgh Math. Soc., série 2, III, 1932, p. 207-219. Zbl0006.14702 · Zbl 0006.14702 · doi:10.1017/S001309150000794X
[2] 2. E. H. BAREISS, Sylvester’s Identity and Multistep Integer Preserving Gaussian Elimination, Math. Comp., 22, 565-578 (1968). Zbl0187.09701 MR226829 · Zbl 0187.09701 · doi:10.2307/2004533
[3] 3. BORCHARDT, Zur Theorie der Elimination und Kettenbruch-Entwichlung, Math. Abh. der Akad. der Wissenschaften zu Berlin, 1878, p. 1-17.
[4] 4. W. S. BROWN, On Euclid’s Algorithm and the Computation of Polynomial Greatest Common Divisors, J.A.C.M., 1971, 18, p. 476-504. Zbl0226.65040 MR307450 · Zbl 0226.65040 · doi:10.1145/321662.321664
[5] 5. W. S. BROWN et J. F. TRAUB, On Euclid’s Algorithm and the Theory of Subresultants, J.A.C.M., 1971, 18, p. 505-514. Zbl0226.65041 MR303684 · Zbl 0226.65041 · doi:10.1145/321662.321665
[6] 6. M. CHARDIN, Un algorithme pour le calcul du résultant de trois polynômes homogènes en trois variables, Centre de Mathématiques et Laboratoire d’informatique, Ecole Polytechnique, 91128 Palaiseau Cedex (prépublication).
[7] 7. G. E. COLLINS, Subresultants and Reduced Polynomial Remainder Séquences, J.A.C.M., 1967, 14, p. 128-142. Zbl0152.35403 MR215512 · Zbl 0152.35403 · doi:10.1145/321371.321381
[8] 8. M. COSTE et M.-F. ROY, Thom’s Lemma, the Coding of Real Algebraic Numbers and the Computation of the Topology of Semi-AIgebraic Sets, J. Symbolic Computations, 1988, 5, p. 121-129. Zbl0689.14006 MR949115 · Zbl 0689.14006 · doi:10.1016/S0747-7171(88)80008-7
[9] 9. L. GONZALEZ, H. LOMBARDI, T. RECIO et M.-F. ROY, Spécialisation de la suite de Sturm et sous-résultants (II), R.A.I..R.O., 1990, p.000-000.
[10] 10. L. GONZALEZ H. LOMBARDI T. RECIO et M.-F. ROY, Sturm-Habicht Sequences, Proceedings I.S.S.A.C, 1989, p. 136-146.
[11] 11. L. GONZALEZ, H. LOMBARDI, T. RECIO et M.-F. ROY, Spécialisation de la suite du Sturm et sous-résultants, version détaillée, CALSYF, Journées du GRECO de Calcul Formel, 1989.
[12] 12. W. HABICHT, Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens, Comm. Math. Helvetici, 1948, 21 p. 99-116. Zbl0029.24402 MR23796 · Zbl 0029.24402 · doi:10.1007/BF02568028
[13] 13. A. LASCOUX, La résultante de deux polynômes, Séminaire d’Algèbre M. P. Malliavin, Lecture Notes in Math., 1984-1985. Zbl0605.13007 MR926297 · Zbl 0605.13007
[14] 14. H. LOMBARDI, Sous-résultants, suite de Sturm, spécialisation, Publications Mathématiques de Besançon (Théorie des Nombres). 1988-89, fascicule 2. MR1052949
[15] 15. R. Loos, Generalized Polynomial Reaminder Sequences, Computer Algebra, Symbolic and Algebraic Computation, Buchberger, Collins, Loos éd., Springer-Verlag, 1982, p. 115-138. Zbl0577.13001 MR728969 · Zbl 0577.13001
[16] 16. M. MIGNOTTE, Some useful bounds, Computer Algebra, Symbolic and Algebraic Computation, Buchberger, Collins, Loos éd., Springer-Verlag, 1982, p. 259-263. Zbl0498.12019 MR728976 · Zbl 0498.12019
[17] 17. C. STURM, Mémoire sur la résolution des équations numériques, Inst. France Sc. Math. Phys., 1835, 6.
[18] 18. J. J. SYLVESTER, On a Theory of Syzygetic Relations of two Rational Integral Functions, Comprising an Application to the Theory of Sturm’s Function, Trans. Roy. Soc. London, 1853; repris dans Sylvester : Collected Math Papers, Chelsea Pub. Comp. NY, 1983, 1, p. 429-586.
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.