Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Improved Budan-Fourier Count for Root Finding

André Galligo 1, 2 
2 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis (1965 - 2019), CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : Given a degree n univariate polynomial f(x), the Budan-Fourier function Vf (x) counts the sign changes in the sequence of derivatives of f evaluated at x. The values at which this function jumps are called the virtual roots of f, these include the real roots of f and any multiple root of its derivatives. This concept was introduced (by an equivalent property) by Gonzales-Vega, Lombardi, Mahe and then studied by Coste, Lajous, Lombardi, Roy .The set of virtual roots provide a good real substitute to the set of complex roots; it depends continuously on the coefficients of f. We will describe a root isolation method by a subdivision process based on a generalized Budan-Fourier count, fast evaluation and Newton like approximations. Our algorithm will provide isolating intervals for all augmented virtual roots of f. For a polynomials with integer coefficients of length size = ~O(n), its bit cost is in ~O (n5). We rely on a new connexity property of the Budan table of f which collects the signs of the iterated derivatives of f.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : André Galligo Connect in order to contact the contributor
Submitted on : Tuesday, December 20, 2011 - 11:07:15 AM
Last modification on : Thursday, August 4, 2022 - 5:05:33 PM
Long-term archiving on: : Wednesday, March 21, 2012 - 2:25:07 AM


Files produced by the author(s)


  • HAL Id : hal-00653762, version 1



André Galligo. Improved Budan-Fourier Count for Root Finding. 2011. ⟨hal-00653762⟩



Record views


Files downloads