Random polynomials and expected complexity of bisection methods for real solving

Details Random polynomials and expected complexity of bisection methods for real solving Random polynomials and expected complexity of bisection methods for real solving

2010-05-12

arxiv.org/abs/1005.2001v2

International Symposium on Symbolic and Algebraic Computation (ISSAC), Munich : Germany (2010)

Computer Science

Symbolic Computation

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Random polynomials and expected complexity of bisection methods for real solving does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random polynomials and expected complexity of bisection methods for real solving, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random polynomials and expected complexity of bisection methods for real solving will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-498956