Random polynomials and expected complexity of bisection methods for real solving

Ioannis Z. Emiris 1 André Galligo 2, 3 Elias Tsigaridas 1, 4, *
* Auteur correspondant
3 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 : Our probabilistic analysis sheds light to the following questions: Why do random polynomials seem to have few, and well separated real roots, on the average? Why do exact algorithms for real root isolation may perform comparatively well or even better than numerical ones? We exploit results by Kac, and by Edelman and Kostlan in order to estimate the real root separation of degree $d$ polynomials with i.i.d.\ coefficients that follow two zero-mean normal distributions: for $SO(2)$ polynomials, the $i$-th coefficient has variance ${d \choose i}$, whereas for Weyl polynomials its variance is ${1/i!}$. By applying results from statistical physics, we obtain the expected (bit) complexity of \func{sturm} solver, $\sOB(r d^2 \tau)$, where $r$ is the number of real roots and $\tau$ the maximum coefficient bitsize. Our bounds are two orders of magnitude tighter than the record worst case ones. We also derive an output-sensitive bound in the worst case. The second part of the paper shows that the expected number of real roots of a degree $d$ polynomial in the Bernstein basis is $\sqrt{2d}\pm\OO(1)$, when the coefficients are i.i.d.\ variables with moderate standard deviation. Our paper concludes with experimental results which corroborate our analysis.
Type de document :
Communication dans un congrès
S. Watt. ISSAC, Jul 2010, Munich, Germany. pp.235-242, 2010, 〈10.1145/1837934.1837980〉
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00482722
Contributeur : Elias Tsigaridas <>
Soumis le : mercredi 12 mai 2010 - 10:54:30
Dernière modification le : vendredi 12 janvier 2018 - 01:48:38
Document(s) archivé(s) le : jeudi 23 septembre 2010 - 12:36:44

Fichiers

egt-issac-10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Ioannis Z. Emiris, André Galligo, Elias Tsigaridas. Random polynomials and expected complexity of bisection methods for real solving. S. Watt. ISSAC, Jul 2010, Munich, Germany. pp.235-242, 2010, 〈10.1145/1837934.1837980〉. 〈inria-00482722v2〉

Partager

Métriques

Consultations de la notice

305

Téléchargements de fichiers

242