Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Univariate real root isolation over a single logarithmic extension of real algebraic numbers

Adam Strzebonski 1 Elias Tsigaridas 2 
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial B ∈ L[x], where L = Q[lg(α)] and α is a positive real algebraic number. The algorithm approximates the coefficients of B up to a sufficient accuracy and then solves the approximate polynomial. For this we derive worst case (aggregate) separation bounds. We also estimate the expected number of real roots when we draw the coefficients from a specific distribution and illustrate our results experimentally. A generalization to bivariate polynomial systems is also presented. We implemented the algorithm in C as part of the core library of mathematica for the case B ∈ Z[lg(q)][x] where q is positive rational number and we demonstrate its efficiency over various data sets.
Document type :
Conference papers
Complete list of metadata

Cited literature [43 references]  Display  Hide  Download

https://hal.inria.fr/hal-01001820
Contributor : Elias Tsigaridas Connect in order to contact the contributor
Submitted on : Saturday, December 24, 2016 - 8:26:01 AM
Last modification on : Wednesday, June 8, 2022 - 12:50:04 PM
Long-term archiving on: : Tuesday, March 21, 2017 - 11:44:54 AM

Files

st-rs-log (1).pdf
Files produced by the author(s)

Identifiers

Citation

Adam Strzebonski, Elias Tsigaridas. Univariate real root isolation over a single logarithmic extension of real algebraic numbers. ACA 2015 - Applications of Computer Algebra, Jul 2015, Kalamata, Greece. pp.425-445, ⟨10.1007/978-3-319-56932-1_27⟩. ⟨hal-01001820v3⟩

Share

Metrics

Record views

247

Files downloads

255