Univariate Real Root Isolation in Multiple Extension Fields

Adam Strzebonski 1 Elias Tsigaridas 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial in $\Ba \in L[y]$, where $L=\QQ(\alpha_1, \dots, \alpha_{\ell})$ is an algebraic extension of the rational numbers. Our bounds are single exponential in $\ell$ and match the ones presented in \cite{st-issac-2011} for the case $\ell=1$. We consider two approaches. The first, indirect approach, using multivariate resultants, computes a univariate polynomial with integer coefficients, among the real roots of which are the real roots of $\Ba$. The Boolean complexity of this approach is $\sOB(N^{4\ell+4})$, where $N$ is the maximum of the degrees and the coefficient bitsize of the involved polynomials. The second, direct approach, tries to solve the polynomial directly, without reducing the problem to a univariate one. We present an algorithm that generalizes Sturm algorithm from the univariate case, and modified versions of well known solvers that are either numerical or based on Descartes' rule of sign. We achieve a Boolean complexity of $\sOB(\min\set{N^{4\ell + 7},N^{2\ell^2+6}})$ and $\sOB( N^{2\ell+4})$, respectively. %% We implemented the algorithms in \func{C} as part of the core library of \mathematica and we illustrate their efficiency over various data sets.
Type de document :
Communication dans un congrès
ISSAC 2012 - 37th ACM International Symposium on Symbolic and Algebraic Computation, Jul 2012, Grenoble, France. ACM, pp.343-350, 2012, <10.1145/2442829.2442878>
Liste complète des métadonnées

https://hal.inria.fr/hal-00776074
Contributeur : Elias Tsigaridas <>
Soumis le : mardi 15 janvier 2013 - 00:46:15
Dernière modification le : mardi 20 septembre 2016 - 01:04:09

Fichier

st-rsmef.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Adam Strzebonski, Elias Tsigaridas. Univariate Real Root Isolation in Multiple Extension Fields. ISSAC 2012 - 37th ACM International Symposium on Symbolic and Algebraic Computation, Jul 2012, Grenoble, France. ACM, pp.343-350, 2012, <10.1145/2442829.2442878>. <hal-00776074>

Partager

Métriques

Consultations de
la notice

191

Téléchargements du document

228