A recursive algorithm for constructing generalized Sturm sequence

DOI10.1007/BF02917135MaRDI QIDQ1841471zbMATH OpenOpenAlexFDO

Authors Hongguang Fu, Lu Yang, Zhenbing Zeng

Publication date 8 May 2002

Published in Science in China. Series E (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02917135

zbMATH Keywords

generalized Sturm sequenceMaplepolynomial remainder sequenceprincipal subresultant coefficientsubresultant polynomial

Mathematics Subject Classification ID

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

Review text

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. \textit{L. González-Vega}, \textit{T. Reico}, \textit{H. Lombardi} and \textit{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 \textit{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.

Recommendations

• The derivation method to calculate the zeros of polynomials
• Spécialisation de la suite de Sturm
• Spécialisation de la suite de Sturm et sous-résultants (I)
• Explicit expressions for Sturm sequences
• Recent advances on determining the number of real roots of parametric polynomials
• Automatic computation of the complete root classification for a parametric polynomial
• Counting positive solutions for polynomial systems with real coefficients
• scientific article; zbMATH DE number 5221564
• A stability test for complex polynomials
• An algebraic algorithm to isolate complex polynomial zeros using Sturm sequences

Cites work

• A complete discrimination system for polynomials
• A complete discrimination system for polynomials with complex coefficients and its automatic generation
• Eine Verallgemeinerung des Sturmschen Wurzelzählverfahrens
• scientific article; zbMATH DE number 1157660 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)

Cited in

(6)

• Counting positive solutions for polynomial systems with real coefficients
• Explicit expressions for Sturm sequences
• Spécialisation de la suite de Sturm et sous-résultants (I)
• A quadratic algebra associated with the Sturm sequence
• Uniqueness of equilibrium in the haber synthesis of ammonia
• Return time complexity of Sturmian sequences

Describes a project that uses

Uses Software

• Maple

This page was built for publication: A recursive algorithm for constructing generalized Sturm sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1841471)