Random Polynomials and Expected Complexity of Real Solving

Title: Random Polynomials and Expected Complexity of Real Solving
Speaker: Dr. Elias Tsigaridas (PolSys group, INRIA Paris-Rocquencourt, France)
Time: 15:00, Thursday, November 1st, 2012
Venue: Lecture Room, 3rd Floor, Building #5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences
Abstract:
We present a probabilistic analysis to shed light to the following questions: Why do random polynomials seem to have few, and well separated real roots, on the average? Why do algorithms based on exact computations for real root isolation perform comparatively well or even better than numerical ones? We exploit results by Kac and by Edelman and Kostlan and we use tools from statistical physics in order to estimate the real root separation of degree d polynomials with i.i.d. coefficients that follow two zero-mean normal distributions, and to obtain the expected (Boolean) complexity of STURM solver. We also prove that the expected number of real roots of a degree d random polynomial in the Bernstein basis is \sqrt{2d}\pm O(1), when the coefficients are i.i.d. variables with moderate standard deviation.

Joint work with Ioannis Emiris and Andre Galligo.