Certified counting of roots of random univariate polynomials
arXiv:1412.1717
Abstract
A challenging problem in computational mathematics is to compute roots of a high-degree univariate random polynomial. We combine an efficient multiprecision implementation for solving high-degree random polynomials with two certification methods, namely Smale's -theory and one based on Gerschgorin's theorem, for showing that a given numerical approximation is in the quadratic convergence region of Newton's method of some exact solution. With this combination, we can certifiably count the number of real roots of random polynomials. We quantify the difference between the two certification procedures and list the salient features of both of them. After benchmarking on random polynomials where the coefficients are drawn from the Gaussian distribution, we obtain novel experimental results for the Cauchy distribution case.
arXiv comment28 pages, 16 figures
References in corpus (9)
- Freezing Transition, Characteristic Polynomials of Random Matrices, and the Riemann Zeta-Function
- Finding All the Stationary Points of a Potential Energy Landscape via Numerical Polynomial Homotopy Continuation Method
- Phase transitions detached from stationary points of the energy landscape
- Tumbling through a landscape: Evidence of instabilities in high-dimensional moduli spaces
- Finding all flux vacua in an explicit example
- Numerical Algebraic Geometry: A New Perspective on String and Gauge Theories
- Enumerating Gribov copies on the lattice
- Energy Landscape of the Finite-Size Mean-field 3-Spin Spherical Model
- Statistics of the Number of Zero Crossings : from Random Polynomials to Diffusion Equation