Random polynomials and expected complexity of bisection methods for real solving

DOI10.1145/1837934.1837980MaRDI QIDQ2946544zbMATH OpenOpenAlexFDO

Authors Ioannis Z. Emiris, Elias P. Tsigaridas, André Galligo

Publication date 17 September 2015

Published in Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.2001

zbMATH Keywords

random polynomialBernstein polynomialexpected complexityreal-root isolationseparation bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

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 $dchoosei$, 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}au)$, where $r$ is the number of real roots and $au$ 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 $sqrt2dpmOO(1)$, when the coefficients are i.i.d. variables with moderate standard deviation. Our paper concludes with experimental results which corroborate our analysis.

Recommendations

• On the number of real solutions of a random polynomial
• On the real roots of a random algebraic polynomial
• Approximation by random complex polynomials and random rational functions
• scientific article; zbMATH DE number 1859213
• On the number of real roots of random polynomials
• Random Polynomials and Approximate Zeros of Newton’s Method
• Real zeros of random algebraic polynomials with binomial elements
• Real roots of random polynomials: expectation and repulsion
• Publication:3031835
• A theorem on random polynomials and some consequences in average complexity

Cites work

• scientific article; zbMATH DE number 3762913 (Why is no real title available?)
• scientific article; zbMATH DE number 45257 (Why is no real title available?)
• scientific article; zbMATH DE number 3490133 (Why is no real title available?)
• scientific article; zbMATH DE number 2038305 (Why is no real title available?)
• scientific article; zbMATH DE number 2142844 (Why is no real title available?)
• scientific article; zbMATH DE number 3015982 (Why is no real title available?)
• scientific article; zbMATH DE number 802623 (Why is no real title available?)
• Differential algebra for derivations with nontrivial commutation rules
• Differential invariants of a Lie group action: syzygies on a generating set
• Differential invariants of conformal and projective surfaces
• Generating differential invariants
• Higher order contact of submanifolds of homogeneous spaces
• Invariants différentiels d'un pseudogroupe de Lie. I
• Invariants différentiels d'un pseudogroupe de Lie. II
• Moving coframes. II: Regularization and theoretical foundations
• Projective-type differential invariants and geometric curve evolutions of KdV-type in flat homogeneous manifolds
• Rational invariants of a group action. Construction and rewriting
• Smooth and algebraic invariants of a group action: Local and global constructions

Cited in

(8)

• Root refinement for real polynomials using quadratic interval refinement
• Around the circular law
• On the expected number of internal equilibria in random evolutionary games with correlated payoff matrix
• New progress in real and complex polynomial root-finding
• Improved bounds for the CF algorithm
• Nearly optimal refinement of real roots of a univariate polynomial
• Univariate real root isolation over a single logarithmic extension of real algebraic numbers
• scientific article; zbMATH DE number 1984134 (Why is no real title available?)

Describes a project that uses

Uses Software

• DIFFALG
• AIDA
• STURM

This page was built for publication: Random polynomials and expected complexity of bisection methods for real solving

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946544)