A Near-Optimal Algorithm for Computing Real Roots of Sparse Polynomials

2014/01/23 by Sagraloff, Michael
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.1401.6011

Abstract

Let p∈ℤ[x] be an arbitrary polynomial of degree n with k non-zero integer coefficients of absolute value less than 2^τ. In this paper, we answer the open question whether the real roots of p can be computed with a number of arithmetic operations over the rational numbers that is polynomial in the input size of the sparse representation of p. More precisely, we give a deterministic, complete, and certified algorithm that determines isolating intervals for all real roots of p with O(k³⋅log(nτ)⋅ log n) many exact arithmetic operations over the rational numbers. When using approximate but certified arithmetic, the bit complexity of our algorithm is bounded by O(k⁴⋅ nτ), where O(⋅) means that we ignore logarithmic. Hence, for sufficiently sparse polynomials (i.e. k=O(log^c (nτ)) for a positive constant c), the bit complexity is O(nτ). We also prove that the latter bound is optimal up to logarithmic factors.

Related

• Efficiently Computing Real Roots of Sparse Polynomials
• Root Refinement for Real Polynomials
• Computing Real Roots of Real Polynomials
• On the Complexity of Real Root Isolation
• Improved complexity bounds for real root isolation using Continued Fractions