Fast real and complex root-finding methods for well-conditioned polynomials

2021/02/08 by Moroz, Guillaume
#FOS: Computer and information sciences #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.2102.04180

Abstract

Given a polynomial p of degree d and a bound κ on a condition number of p, we present the first root-finding algorithms that return all its real and complex roots with a number of bit operations quasi-linear in d log²(κ). More precisely, several condition numbers can be defined depending on the norm chosen on the coefficients of the polynomial. Let p(x) = ∑_k=0^d a_k x^k = ∑_k=0^d √(\binom d k) b_k x^k. We call the condition number associated with a perturbation of the a_k the hyperbolic condition number κ_h, and the one associated with a perturbation of the b_k the elliptic condition number κ_e. For each of these condition numbers, we present algorithms that find the real and the complex roots of p in O(dlog²(dκ) polylog(log(dκ))) bit operations.Our algorithms are well suited for random polynomials since κ_h (resp. κ_e) is bounded by a polynomial in d with high probability if the a_k (resp. the b_k) are independent, centered Gaussian variables of variance 1.

Related

• Polynomial root-finding algorithms and branched covers
• Accelerated Approximation of the Complex Roots of a Univariate\n Polynomial (Extended Abstract)
• Accelerated Approximation of the Complex Roots and Factors of a Univariate Polynomial
• Real Polynomial Root-finding by Means of Matrix and Polynomial Iterations
• Polynomial Root-Finding and Algebraic Eigenvalue Problem