Random polynomials and expected complexity of bisection methods for real solving
| Autor: | André Galligo, Elias P. Tsigaridas, Ioannis Z. Emiris |
|---|---|
| Přispěvatelé: | Department of Informatics and Telecomunications [Kapodistrian Univ] (DI NKUA), National and Kapodistrian University of Athens (NKUA), Laboratoire Jean Alexandre Dieudonné (JAD), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS), Geometry, algebra, algorithms (GALAAD), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (... - 2019) (UNS), Department of Computer Science [Aarhus], S. Watt, Université Nice Sophia Antipolis (1965 - 2019) (UNS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) |
| Rok vydání: | 2010 |
| Předmět: |
Computer Science - Symbolic Computation
FOS: Computer and information sciences Polynomial ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY 0102 computer and information sciences Expected value Symbolic Computation (cs.SC) 01 natural sciences Standard deviation Normal distribution separation bound Probabilistic analysis of algorithms 0101 mathematics Mathematics Discrete mathematics expected complexity [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] real-root isolation Degree (graph theory) 010102 general mathematics Bernstein polynomial Difference polynomials 010201 computation theory & mathematics Random polynomial ACM: I.: Computing Methodologies/I.1: SYMBOLIC AND ALGEBRAIC MANIPULATION |
| Zdroj: | Preceedings of International Symposium on Symbolic and Algebraic Computation ISSAC ISSAC, Jul 2010, Munich, Germany. pp.235-242, ⟨10.1145/1837934.1837980⟩ Scopus-Elsevier Emiris, I Z, Galligo, A & Tsigaridas, E 2010, ' Random polynomials and expected complexity of bisection methods for real solving ', International Symposium on Symbolic and Algebraic Computation, pp. 235-242 . https://doi.org/10.1145/1837934.1837980 |
| DOI: | 10.48550/arxiv.1005.2001 |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|