Random polynomials and expected complexity of bisection methods for real solving

DOI10.1145/1837934.1837980zbMATH Open1321.68308arXiv1005.2001OpenAlexW2144292545MaRDI QIDQ2946544FDOQ2946544

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Rational invariants of a group action. Construction and rewriting
• Title not available (Why is that?)
• Differential invariants of a Lie group action: syzygies on a generating set
• Moving coframes. II: Regularization and theoretical foundations
• Title not available (Why is that?)
• Differential algebra for derivations with nontrivial commutation rules
• Generating differential invariants
• Smooth and algebraic invariants of a group action: Local and global constructions
• Invariants différentiels d'un pseudogroupe de Lie. II
• Differential invariants of conformal and projective surfaces
• Projective-type differential invariants and geometric curve evolutions of KdV-type in flat homogeneous manifolds
• Higher order contact of submanifolds of homogeneous spaces
• Invariants différentiels d'un pseudogroupe de Lie. I
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

• On the expected number of internal equilibria in random evolutionary games with correlated payoff matrix
• Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers
• New progress in real and complex polynomial root-finding
• Around the circular law
• Root refinement for real polynomials using quadratic interval refinement
• Nearly optimal refinement of real roots of a univariate polynomial
• Title not available (Why is that?)
• Improved bounds for the CF algorithm

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)