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, 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, ...
Liste complète des métadonnées

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-00653762
Contributor : André Galligo <>
Submitted on : Tuesday, December 20, 2011 - 11:07:15 AM
Last modification on : Friday, January 12, 2018 - 1:48:44 AM
Document(s) archivé(s) le : Wednesday, March 21, 2012 - 2:25:07 AM

File

RootFindingGalligo.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00653762, version 1

Collections

Citation

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

Share

Metrics

Record views

231

Files downloads

692