Univariate real root isolation in an extension field and applications
Résumé
We present algorithmic, complexity and implementation results for
the problem of isolating the real roots of a univariate polynomial
in $B_{\alpha} \in L[y]$, where $L=\QQ(\alpha)$ is a simple
algebraic extension of the rational numbers.
We revisit two approaches for the problem. In the first
approach, using resultant computations, we perform a reduction to a
polynomial with integer coefficients and we deduce a bound of
$\sOB(N^{8})$ for isolating the real roots of $B_{\alpha}$, where
$N$ is an upper bound on all the quantities (degree and bitsize) of
the input polynomials.
The bound becomes $\sOB(N^{7})$ if we use Pan's algorithm for isolating
the real roots.
%%
In the second approach we isolate the real roots working directly on
the polynomial of the input. We compute improved separation bounds
for the roots and we prove that they are optimal, under mild
assumptions. For isolating the real roots we consider a modified
Sturm algorithm, and a modified version of \func{descartes}'
algorithm. For the former we prove a Boolean complexity bound of
$\sOB(N^{12})$ and for the latter a bound of
$\sOB(N^{5})$.
%%
We present aggregate separation bounds and complexity results for
isolating the real roots of all polynomials $B_{\alpha_k}$, when
$\alpha_k$ runs over all the real conjugates of $\alpha$. We show
that we can isolate the real roots of all polynomials in
$\sOB(N^5)$.
%%
Finally, we implemented the algorithms in \func{C} as part of the core
library of \mathematica and we illustrate their efficiency over
various data sets.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...