Certified counting of roots of random univariate polynomials

arXiv1412.1717MaRDI QIDQ6256995FDOQ6256995

Leonardo Robol, Joseph Cleveland, Ian Haywood, Dhagash Mehta, Taylor Schlenk, A. P. Morse, Jeffrey Dzugan, Jonathan D. Hauenstein

Publication date: 4 December 2014

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 $alpha$-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.

This page was built for publication: Certified counting of roots of random univariate polynomials

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